42. After the rain

Feeling or a special topic, monotonous Stack method, define the type of a Stack of low-lying place, does not need to be 10 a Stack, in the judgment, whether need to overall judgment anvil-shaped or a low status (10 whether also can form a puddle, judgment is whether there are elements in low areas). Second, it is necessary to determine whether a low-lying area can be formed at present (stack.peek() takes out the value, and here use if (stack.isempty ()) to determine that there is still rain).

import java.util.Stack;

/**
 * DropWater
 *
 * @author Scottish
 * @date2021/5/21 * /
public class DropWater {

    public static void main(String[] args) {
        int[] height = new int[] {2.0.0.0.1.2};
        / / int [] height = new int [],1,0,2,1,0,1,3,2,1,2,1 {0}.
        System.out.println(trap(height));
    }


    public static int trap(int[] height) {
        if(height.length == 0) {
            return 0;
        }
        int area = 0;
        Stack<Integer> lowIsland = new Stack<>();
        for(int i = 0 ; i < height.length ; i++) {
            while(! lowIsland.isEmpty() && height[i] > height[lowIsland.peek()]) {int cur = lowIsland.pop();
                if(lowIsland.isEmpty()) {
                    break;
                }
                int left = lowIsland.peek();
                int h = Math.min(height[i],height[left]) - height[cur];
                int w = i - left - 1;
                System.out.println("i: " + i + "left: " + left);
                area = area + h * w;
            }
            lowIsland.push(i);
        }
        returnarea; }}Copy the code