Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Construct the axes based on the input array numbers and figure out how much water the axes can hold in the container.”

Title link: Source: LeetCode

Link: leetcode-cn.com/problems/co…

2

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: You cannot tilt the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] In this case, the maximum amount of water the container can hold (shown in blue) is 49.Copy the code
Example 2: Input: height = [1,1] Output: 1Copy the code
Example 3: input: height = [1,2,1] output: 2Copy the code
Example 4: Input: height = [4,3,2,1,4] Output: 16Copy the code

Second, the problem solving

1. Analysis of ideas

At the beginning, set two Pointers I and J to point to the left and right sides of the array respectively. The height of the sink plate they point to is H [I] and H [j] respectively. At this time, the capacity is S[I,j], because the capacity is determined by the short plate at both ends, the area formula can be obtained:

S(i,j) = min(h[i],h[j]) x (j-i)

At this point, we need to move the pointer that points to the smaller number (capacity = the smaller value of the two Pointers * the distance between the Pointers).

Points to a larger number can then be used as the boundary of the container until the moving pointer points to a larger number than the current boundary, and another pointer is moved.

So, we calculate the maximum value of the container each time using the left and right boundaries of the double pointer, that is, the array.

2. Code implementation

Double pointer method reference code:

public class Solution 
{
    public int MaxArea(int[] height) 
    {
        int l = 0, r = height.Length - 1, ans = - 1, curr = - 1;
        while (l <= r) {
            curr = (r - l) * Math.Min(height[l], height[r]);
            ans = Math.Max(curr, ans);
            if (height[l] < height[r]) l++;
            else r--;
        }
        returnans; }}Copy the code

3. Time complexity

Time complexity: O(N)

A double pointer traverses the entire array at most once.

Space complexity: O(1)

Just extra constant level space.

Third, summary

To be honest, before solving this problem, I didn’t even know what double pointer was, so I couldn’t think of using double pointer. For brushing the problem, it is very important to learn from others’ excellent problem-solving ideas, and to understand and implement them.

So-called solution problem train of thought, it is what you solve problem solution much, have train of thought of course. For some questions the solution of the idea is not not, is not hard to think can come out, so, this is the meaning of brush questions, brush this topic, the topic is summed up, these ingenious ideas we can learn naturally.

Therefore, to sum up the idea of double Pointers, the most important point is that double Pointers are mostly the optimization of the double cycle, so when using violence to solve the double cycle, you can think about whether you can use double Pointers to solve the problem.

Secondly, is the double pointer limit to meet the conditions, must be found according to the problem of the limit, this condition is also the movement of the double pointer condition, is also the basis of the idea of the double pointer.