接雨水（Leetcode42）

例题：

题目说了，给定n个宽度为1的柱子，height数组中的每个元素表示每个柱子的高度。

只要柱子之间存在凹槽，就能接住雨水。

在解决这道题目之前，我们先了解一下单调递减栈。（由栈底到栈顶逐渐递减）

刚开始栈是空的，如果往栈中依次加入4、3、2元素，可以直接加入，当加入元素5时，因为5比2、3、4都要大，要把这三个元素先弹出栈，再加入元素5。如下图：

单调递减栈代码：

import java.util.LinkedList;

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

    public static int trap(int[] height) {
        LinkedList<Data> stack = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            Data right = new Data(height[i], i);
            while(!stack.isEmpty() && stack.peek().height < height[i]){
                stack.pop();
            }
            stack.push(right);
            System.out.println(stack);
        }
        return -1;
    }

    static class Data{
        int height; //柱子的高度
        int i;  //柱子索引

        public Data(){

        }

        public Data(int height, int i) {
            this.height = height;
            this.i = i;
        }

        @Override
        public String toString() {
            return String.valueOf(height);
        }
    }
}

运行结果：（左边表示栈顶）

好，接下来利用这个单调递减栈来解决刚才的例题：

核心思想：

依次把给出的元素加入栈中，当加入一个元素时，如果发现需要弹出元素，表示遇到了一个凹陷的位置，此时应该计算雨水容量。

? ? ?

图中左边表示栈底，当新加入的元素（right）比栈顶大时，先把栈顶元素弹出，被弹出的元素记为pop，此时需要检查pop的左边是否还有元素，若有元素表示存在凹陷，应该计算雨水容量。

①先计算宽：j - i - 1

②再计算高度：注意右边的柱子right不一定比left高，pop的高度不一定为0，我们应该从right和left中选出高度较小的（min），Math.min(right, left), 然后再用（min的高度 - pop的高度）与上面计算的宽相乘就能得出雨水的容量。

代码实现：

import java.util.LinkedList;

public class TrappingRainWarterLeetcode42 {
    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
        //System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5})); // 9
    }

    public static int trap(int[] heights) {
        LinkedList<Data> stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < heights.length; i++) {
            Data right = new Data(heights[i], i);
            while(!stack.isEmpty() && stack.peek().height < right.height){
                Data pop = stack.pop();
                Data left = stack.peek();
                if(left != null && left.height > pop.height){ //计算水的容量
                    int width = right.i - left.i - 1;
                    int height = Math.min(right.height, left.height) - pop.height;
                    sum += width * height;
                }
            }
            stack.push(right);
        }
        return sum;
    }

    static class Data{
        int height; //柱子的高度
        int i;  //柱子索引

        public Data(){

        }

        public Data(int height, int i) {
            this.height = height;
            this.i = i;
        }

        @Override
        public String toString() {
            return String.valueOf(height);
        }
    }
}