This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Interview question 17.21. The amount of water in the histogram

Given a histogram (also known as a bar chart), suppose someone poured water from it in a steady stream. How much water could the histogram eventually hold? The width of the histogram is 1.

Above is the histogram represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], which in this case can be followed by six units of water (the blue part represents water). Thanks to Marcos for contributing this image.

Example:

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

Their thinking

Maintain a monotonically decreasing stack, when traversed to the element is greater than the stack element, the top of the stack element at this time found its left and right of the first wall height is higher than it, the stack of two elements and the current element to form a rain area.

Practice:

  1. If height[I] <= top element, then the height of the current traversed wall is pushed onto the stack
  2. If height[I] > top element, the current top element is removed from the stack top = stack.pop(), and height[I] is the first wall to the right of height[top] that is taller than it, and the new top elementl=stack.peek()Height [top] is the first wall on the left that is higher than height (the lower of the two walls)Math.min(height[l],height[i])-height[top]And then find the width of the raini-l-1

code

class Solution {
 public int trap(int[] height) {

        Stack<Integer> stack=new Stack<>();
        int n=height.length,res=0;
        for(int i=0; i<n; i++) {while(! stack.isEmpty()&&height[i]>height[stack.peek()]) {int top=stack.pop();
                if(stack.isEmpty())
                    break;
                int l=stack.peek();
                int weight=i-l-1;
                int h=Math.min(height[l],height[i])-height[top];
                res+=h*weight;
            }
            stack.push(i);
        }
        returnres; }}Copy the code

Time complexity: O(n), where n is the length of array height. Each subscript from 0 to n−1 is pushed and unpushed at most once.

Space complexity: O(n), where n is the length of array height. The space complexity depends mainly on the stack space, and the stack size cannot exceed N.