Leetcode interview question 17.21. water volume double pointer of histogram, monotonic stack /hard

---

1.Description

Given a histogram ( Also known as histogram ), Suppose someone pours water from above , Finally, how much water can be stored in the histogram ? The width of the histogram is 1.

---

2.Example

Above is an array of [0,1,0,2,1,0,1,3,2,1,2,1] The histogram of representation , under these circumstances , Can connect 6 Units of water （ The blue part shows water ）. thank Marcos Contribute to this map .

 Input : [0,1,0,2,1,0,1,3,2,1,2,1]
 Output : 6

---

3.Solution

1. Double pointer

Define two pointers to traverse from left and right sides to the middle , Save the highest point and add water during traversal .
When I wrote it myself, I didn't add the one with comments in the code if Conditions , Cause error , it is to be noted that .

Reference resources ： Add link description

class Solution {
    
    public static int trap(int[] height) {
    
        int N = height.length;
        if(N<2) {
    
        	return 0;
        }
        int left=0,right = N-1;
        int lHeight = 0,rHeight = 0;
        int res = 0;
        while(left<right) {
    
        	// The condition here is ： When the right side is higher than the left side, calculate the water volume on the left , When the left is higher than the right, calculate the water volume on the right ,
        	// That is, when calculating the water volume on the left, ensure that there must be a wall higher than the left on the right to form a pit with the left , Otherwise, the water volume cannot be calculated ; The same is true on the right .
        	if(height[left]<height[right]) {
    
        		if(height[left]<lHeight) {
    
        			res += lHeight - height[left];
        		}else {
    
        			lHeight = height[left];
        		}
        		left++;
        	}else {
    
        		if(height[right]<rHeight) {
    
        			res += rHeight - height[right];
        		}else {
    
        			rHeight = height[right];
        		}
        		right--;
        	}
        }
        return res;
    }
}

2. Monotonic stack

Maintain a monotone stack , The monotone stack stores subscripts , Satisfy the array corresponding to the subscript from the bottom of the stack to the top of the stack height Decreasing elements in .

Traversing the array from left to right , Traverse to subscript i when , If there are at least two elements in the stack , The top element of the stack is top,top The next element of is left, There must be height[(left > height(top]. If height[i]> height)top), Then you get an area that can receive rainwater , The width of this area is i- left-1, Height is min(height[left , heightji]) - height(top], According to the width and height, the amount of water that can be connected in this area can be calculated .

In order to get left, Need to put top Out of the stack . In the face of top After calculating the amount of water that can be connected ,left Become new top, Repeat the above operation , Until the stack becomes empty , Or the subscript at the top of the stack corresponds to height The element in is greater than or equal to height[i].

On the subscript i After calculating the amount of water that can be connected , take i Push , Continue to traverse the following subscripts , Calculate the amount of water that can be connected . After traversing, you can get the total amount of water that can be connected .

See the official explanation for the moving picture ： Add link description

class Solution {
    
    public int trap(int[] height) {
    
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
    
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
    
                int top = stack.pop();
                if (stack.isEmpty()) {
    
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
}