042 - Trapping Rain Water

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!
Hide Tags
Array Stack Two Pointers
Hide Similar Problems
(M) Container With Most Water (M) Product of Array Except Self
 
这道题是在(M) Container With Most Water后面做的，做的时候习惯性地想着要求那个坑里放的水最多，
所以一开始做了一个解法，是分别计算每个坑里的水，再累积所有坑来得到总数的。
跑下来虽然也是8 ms，但总觉得繁琐。
感觉应该可以像(M) Container With Most Water一样，用两头逼近的方法，但是没有细想……
看了一下讨论区，确实是可以这么弄的，因为不需要比较哪个坑里放的水多嘛。
所以又写了一个两头逼近的，代码上简洁很多，每次比较两头的高度，用小的来当做newlevel，
如果newlevel比之前达到的level小，那就说明可以装水了，数量是 level – newlevel，
如果大，那就意味着 level 被提高了，更新 level 即可。
然后移动 level 小的一端，这时候跟(M) Container With Most Water不同的是，不是找一个比它大的，
而是要一步一步地移动，因为比它小的要装水，比它大的可能又影响要不要更新 level，所以只能逐步移动。
 
class Solution {
public:
    int trap(vector<int>& height) {
        int sz=height.size();
        int rst=0;
        if(sz)
        {
            int idx1=0, idx2=sz-1, level=0, newlevel=0;
            while(idx1 < idx2)
            {
                newlevel = min(height[idx1], height[idx2]);
                if(newlevel > level)
                    level = newlevel;
                else
                    rst += level - newlevel;                   //calc water if newlevel is lower
                (newlevel == height[idx1]) ? idx1++ : idx2— ;  //move lower idx closer
            }
        }
        return rst;
    }

    int trap_peaks(vector<int>& height) {
        int sz=height.size();
        int rst=0;
        if(sz>2)
        {
            int sum=0, idx1=0, idx2=0, idx=0, peak1=0, peak2=0;
           
            //find first peak
            while((idx1<sz-1) && (height[idx1+1]>=height[idx1]))
                idx1++;
            peak1 = height[idx1];
            idx2 = idx1;
           
            while(idx1<sz-1)
            {
                //find next peak
                idx = idx2;
                bool done=true;                             //for early quit
                while((idx<sz-1) && (peak1 >= height[idx]))
                {
                    idx++;
                    if(peak2 <= height[idx])                //update peak2 with bigger number
                        peak2 = height[idx], idx2 = idx;
                    done &=(height[idx]<height[idx-1]);     //set false once meet a number bigger
                }
                if(done || !peak2)  //early quit if the rest is in descending order or all the same.
                    break;
               
                //calculation possible water between them
                int top = min(peak1, peak2);
                for(int ii=idx1+1; ii<idx2; ++ii)
                    rst += (top-height[ii]);

                //reset for next round
                if(peak2)  //keep peak1 there if peak2 is zero.                {
                    peak1 = peak2;
                    idx1 = idx2;
                    peak2 = 0;
                }
            }
        }
        return rst;
    }
};
8 ms, 8 ms.