LeetCode42 - 接雨水（难度：困难）

链接：https://leetcode-cn.com/problems/trapping-rain-water
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;

        Stack<Integer> helpStack = new Stack<>();
        int n = height.length;
        // 左右边界
        int[] left = new int[n];
        int[] right = new int[n];
        // Arrays.fill(right, n);
        int maxHeight = -1;
        // 遍历确定左右边界
        for(int i=0;i<height.length; i++) {
            while(!helpStack.isEmpty() && height[helpStack.peek()] < height[i]) {
                helpStack.pop();
            }
            left[i] = helpStack.isEmpty()?-1:helpStack.peek();
            if(helpStack.isEmpty() || height[helpStack.peek()] < height[i]){
                helpStack.add(i);
            }
            if(maxHeight < height[i]) {
                maxHeight = height[i];
            }
        }
        helpStack.clear();
        for(int j=height.length-1;j>=0; j--) {
            while(!helpStack.isEmpty() && height[helpStack.peek()] <= height[j]) {
                helpStack.pop();
            }
            right[j] = helpStack.isEmpty()?n:helpStack.peek();
            if(helpStack.isEmpty() || height[helpStack.peek()] < height[j]){
                helpStack.add(j);
            }
        }

        int result = 0;
        for(int i=0; i<height.length; i++) {
            if(left[i] == -1 || right[i] == n) {
                continue;
            }
            int abs = Math.abs(height[left[i]] - height[right[i]]);
            result += (maxHeight - abs - height[i]);
        }
        return result;
    }
}