【字节专题】leetcode 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

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

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

逻辑：

1. 当前高度小于等于栈顶高度，入栈，指针后移。
2. 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

动态规划

首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）

public int trap(int[] height) {
          
   
    int sum = 0;
    int[] max_left = new int[height.length];
    int[] max_right = new int[height.length];

    for (int i = 1; i < height.length - 1; i++) {
          
   
        max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
    }
    for (int i = height.length - 2; i >= 0; i--) {
          
   
        max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
    }
    for (int i = 1; i < height.length - 1; i++) {
          
   
        int min = Math.min(max_left[i], max_right[i]);
        if (min > height[i]) {
          
   
            sum = sum + (min - height[i]);
        }
    }
    return sum;
}

栈

public int trap(int[] height) {
          
   
    int sum = 0;
    Stack<Integer> stack = new Stack<>();
    int cur = 0;
    while (cur<height.length){
          
   
        while (!stack.empty() && height[cur]>height[stack.peek()]){
          
   
            int h = height[stack.peek()];
            stack.pop();
            if (stack.empty())
                break;
            int distance = cur-stack.peek()-1;
            int min = Math.min(height[stack.peek()], height[cur]);
            sum = sum + distance*(min-h);
        }
        stack.push(cur);
        cur++;
    }
    return sum;
}