Trapping Rain Water

浏览数：22 / 时间：2015年06月11日

https://leetcode.com/problems/trapping-rain-water/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

技术分享

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

解题思路：

这题我一次AC敢信么，有人说leetcode其实最大的魅力就在于看到pending-judging-accept，绿色的字一闪，神清气爽。

这题之前在集中做two pointers的题目的时候尝试做过，题目看完想了会儿，没思路就放弃了。今天前面做 Candy 这道题的时候看到网友说这道题和它很像，都是从两头分别扫描两次，才开始又思考怎么做。

Candy 也是我自己写出来的，又有了提示，以为能轻松点，可还是想了很久。受 Candy 思路的影响，开始一直在考虑如何利用相邻两个值和当前值的大小关系来立刻确定当前可以盛水的高度，百思不得其解。后来重新考虑人脑一般是如何考虑这个问题的。

看上面的图，我们人眼总是在最大宽度的可能上，确定左右两个边界，在它们内部的值，都比这两个值小。那么这个内部就是一个坑，坑的高度就是这两个值中比较小的那个。于是，敏感的想到，这个过程似乎可以用上面说的从左到右和从右到左扫描两次来解决。

首先，从左至右扫描，记录当前遇到的最大值topSoFar。如果topSoFar比当前值A[i]大，代表他可能就是当前的盛水高度top[i]。否则就用当前的A[i]去更新topSoFar和当前的盛水高度top[i]。

为什么说可能？那么什么情况下是，什么情况下不是？再看图，答案是，如果当前i的右侧出现一个比i处topSoFar大的A[j]（j > i），当前的top[i]就是成立的。这不正是从右至左再扫描一遍吗？

那么第二遍，从右至左，不断记录当前遇到的最大值topSoFar。只有topSoFar比top[i]大的，top[i]才有效。因为它代表i处右侧有一个更高的柱子。比如图中中间的蓝色大坑。如果topSoFar比top[i]小，就用topSoFar去更新top[i]。也就是用上面的思路反过来更新top[i]，因为上面已经扫描过，此时i左侧必然有一个比i处topSoFar更高的柱子，所以当前的topSoFar一定是此处的盛水高度，比如图中最后一块蓝色。

public class Solution {
    public int trap(int[] A) {
        int[] top = new int[A.length];
        if(A.length == 0 || A.length == 1){
            return 0;
        }
        int topSoFar = A[0];
        //从左到右，topSoFar比当前大，当前的top就是topSoFar
        for(int i = 0; i < A.length; i++){
            if(A[i] <= topSoFar){
                top[i] = topSoFar;
            }else{
                topSoFar = A[i];
                top[i] = A[i];
            }
        }
        
        //从右到左，只有topSoFar比top[i]大的，top[i]才有效，否则top[i]就是topSoFar
        topSoFar = A[A.length - 1];
        for(int i = A.length - 1; i >= 0; i--){
            if(A[i] > topSoFar){
                topSoFar = A[i];
            }
            if(topSoFar < top[i]){
                top[i] = topSoFar;
            }
        }
        
        int area = 0;
        for(int i = 0; i < A.length - 1; i++){
            area += top[i] - A[i];
        }
        return area;
    }
}