LeetCode刷题【42】接雨水

给定 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

 

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

\n

题解

看到题目第一个想到的想法是，找峰值，找到峰值之后，找下一个峰值，这样计算两个峰值之间能够的储水量。然后接下来再去后面继续找峰值，但是新的峰值和前面的峰值之间的储水面积之间是有可能有重合的。

那么有什么办法来计算去掉重合的面积嘛？标记已计算部分也行可行，但是计算起来比较麻烦。拿自己凑的一个数组举例如图数组【7,5,4,1,3,6,2,9】

如果按照之前的思路可以得到这样的情况

后面的复杂形状的计算逻辑有点麻烦，但是这个时候换了个想法看了下。我们其实可以横着来计算，思路都在这张图上了。

依旧是找到第一个峰值，左边的都可以丢掉不管，因为第一个峰值左边的部分储不了水。从峰值开始，每个索引的值按照单调递减入栈，当有新的值比栈顶的值大的时候说明有开始呈上升趋势了，有开始上升的时候就说明这个时候是可以储水的了。

比如图中的索引4位置的值是3，当前栈内元素，按照从栈顶到栈底的顺序依次为1,4,5,7（实际栈内存的索引位置，后面默认都是不做额外说明）。

则可以计算得到A区域的面积，栈顶元素弹出，此时最新栈顶元素为4，而当前的3与4之间要储水的话，需要取小的一个，就是3，再减去之前弹出的栈顶元素1作为底部高度，那么这段区间可以储水面积就是3×1=3。并把3压入栈。

再往后到了索引5的位置，此时栈内元素为3,4,5,7。因为6大于3，把栈顶元素3出栈，按照之前同样的逻辑，6和此时栈顶的4比较取4，那么就得到了图中B区域的面积（4-3）x（5-2-1） = 2。继续和栈顶元素比较，6大于4，将4弹出，相同的操作，得到C区域的面积，同样的算出D区域的面积。最终将5位置6压入栈。

此时栈中元素为6,7。然后来到了索引6，索引6位置2小于此时小于栈顶的6，直接压入栈。之后到了索引7，再算出E，F区域的面积。最终即为所求总储水量。

代码

import java.util.ArrayDeque;
import java.util.Deque;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int area = 0;

    public int trap(int[] arr) {
        if (null==arr||arr.length==0)return area;
        int left = 0;
        int index = 0;
        //找出第一个左边
        while (index < arr.length-1){
            if (arr[index] >= arr[left]){
                left = index;
            }else{
                break;
            }
            index++;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(left);
        //此时的left一定是第一个最高点
        for (int currentIndex = left; currentIndex < arr.length; currentIndex++) {
            if (currentIndex > 0 && arr[currentIndex]>arr[currentIndex-1]){
                while (!deque.isEmpty() && arr[currentIndex] >= arr[deque.peekLast()]){
                    int bottomIndex = deque.pollLast();
                    if (deque.isEmpty()){
                        break;
                    }
                    int leftIndex = deque.peekLast();
                    int height = Math.min(arr[currentIndex],arr[leftIndex]) - arr[bottomIndex];
                    int width = currentIndex - leftIndex - 1;
                    area += height * width;
                }

            }
            deque.offerLast(currentIndex);
        }
        return area;
    }
}
//leetcode submit region end(Prohibit modification and deletion)