[Li Kou brush questions] 11 Container holding the most water //42 Rain water connection

  subject ：

Given a length of n Array of integers for  height . Yes  n  Vertical line , The first i The two ends of the line are  (i, 0)  and  (i, height[i]) .

Find two of them , Make them  x  A container of shafts can hold the most water .

Return the maximum amount of water that the container can store .

explain ： You can't tilt the container .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/container-with-most-water

  When I saw this problem, the first thing in my mind was to solve it with monotone stack ： Because I want to seek the maximum , Find two wires , Use monotone decreasing stack to judge ... Make a judgment when entering the stack , If it's bigger than the top of the stack , Then the top elements of the stack will pop up continuously , The result of the calculation is ; If it is smaller than the top element of the stack, add it directly ; Until the end of the traversal , The whole stack is monotonically decreasing , Then they are processed together until the top element of the stack is empty .（ In the process, I recorded the elements at the bottom of the stack ）

class Solution {
    public int maxArea(int[] height) {
        // Monotone stack problem , Monotonically decreasing stacks 
        // What holds the most water depends on the short side , Not the long side 
        // So make a judgment when entering the stack , If it's bigger than the top of the stack , Then the top elements of the stack will pop up continuously , Calculate the product from this edge to the edge of the top element of the stack , Find the maximum , Then add this edge to the stack 
        // If it is smaller than the top element of the stack, it is directly added to the stack 
        // Finally, handle the elements in the stack , Until the stack element is empty 
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        // Save the maximum stack bottom element 
        int maxLow = 0;
        for(int i = 0;i < height.length;i++){
            if(stack.size() == 0) {
                stack.push(i);
                maxLow = i;
            }
            if(stack.size() != 0 && height[stack.peek()] >= height[i]) stack.push(i);
            // If the element is larger than the top of the stack , Then the calculation results of the elements at the top of the stack are continuously popped up 
            // Notice why while
            while(stack.size() != 0 && height[stack.peek()] < height[i]){
                res = Math.max(res,height[stack.peek()]*(i-stack.pop()));
            }
            // Add this element to the stack 
            if(stack.size() == 0) maxLow = i;
            stack.push(i);
        }
        // Finally, the remaining elements in the stack are processed , The top element of the stack is the smallest element , The bottom of the stack is the largest element 
        while(stack.size() != 0){
            res = Math.max(res,height[stack.peek()]*(stack.pop()-maxLow));
        }
        return res;
    }
}

Then I found out that it was only 24 A use case ：

  such as [1,2,1] Such use cases cannot pass , exactly , because 1 After adding to the stack , Judge 2 When , because 2 Than 1 Big , Will pop up 1, Then the monotonically decreasing stack starts from 2 Start , Obviously this is wrong , The result should be the beginning 1 To the end 1.

I haven't figured out how to solve it with monotone stack ... Because this way of thinking is really wrong , There seems to be a similar problem , I'll update it later ......

Then I looked at the analysis , The answer is to use double pointers .

In each state , Whether the long board or the short board narrows one grid to the middle , Will cause the sink Bottom edge width -1−1​ shorter ：

① If inward Move the short board , The short board of the sink min(h[i], h[j])min(h[i],h[j]) May be bigger , Therefore, the area of the next tank may increase .
② If inward Move the long board , The short board of the sink min(h[i], h[j])min(h[i],h[j])​ Constant or smaller , So the area of the next sink must be smaller .
therefore , Initialize the double pointer to separate the left and right ends of the sink , Move the short board inward one grid in each cycle , And update the maximum area , Until the two pointers meet and jump out ; You can get the maximum area .

Code ：

class Solution {
    public int maxArea(int[] height) {
         int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

anthracene ... Really good concise code ...

42. Rainwater collection

  Monotonically decreasing stack implementation ：

class Solution {
    public int trap(int[] height) {
        // Monotonically decreasing stacks 
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        for(int i = 0;i < height.length;i++){
            if(stack.size() == 0) {
                stack.push(i);
            }
            if(stack.size() != 0 && height[stack.peek()] >= height[i]) stack.push(i);
            // If the element is larger than the top of the stack , Then the calculation results of the elements at the top of the stack are continuously popped up 
            // Notice why while
            while(stack.size() != 0 && height[stack.peek()] < height[i]){
               int mid = stack.pop();// The middle element 
               if(stack.size() != 0){
                   int h = Math.min(height[stack.peek()],height[i]) - height[mid];
                   int w = i - stack.peek() - 1;// Note that only the width in the middle , So we need to reduce 1
                   res += h * w;
               }

            }
            // Add this element to the stack 
            stack.push(i);
        }
        return res;
    }
}

The following one I use monotone decrement stack will not make mistakes , Because I only need to find the left and right boundaries of the containers that can receive water at present , It has nothing to do with the columns in front , And the question above , It may be infinite between two short edges on the boundary , Using the monotone stack to judge and pop up elements will have problems .