原题链接：42. 接雨水 – 力扣（LeetCode）

双指针优化思路：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        //纪录某个节点左右最高的高度
        int[] lHeight = new int[n];
        int[] rHeight = new int[n];
        lHeight[0] = height[0];
        rHeight[n - 1] = height[n - 1];
        for (int i = 1; i < n; i++) {
            lHeight[i] = Math.max(height[i], lHeight[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rHeight[i] = Math.max(height[i], rHeight[i + 1]);
        }
        int ans = 0;
        for(int i = 0;i<n;i++){
            int count = Math.min(lHeight[i],rHeight[i]) - height[i];
            if(count>0) ans+=count;
        }
        return ans;
    }
}

单调栈：

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int n = height.length;
        if (n <= 2)
            return 0;
        int ans = 0;
        for (int i = 1; i < n; i++) {
            int top = stack.peek();
            if (height[i] < height[top]) {
                stack.push(i);
            } else if (height[i] == height[top]) {
                stack.pop();
                stack.push(i);
            } else {
                int rHeight = height[i];
                while (!stack.isEmpty() && rHeight > height[top]) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int l = stack.peek();
                        int h = Math.min(height[l], rHeight) - height[mid];
                        int w = i - l - 1;
                        int hold = h * w;
                        if (hold > 0)
                            ans += hold;
                        top = stack.peek();
                    }
                }
                stack.push(i);
            }
        }
        return ans;
    }
}