[LeetCode] 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!

思路1：stack解法

能积水的地方必然是一个中间低两边高的凹陷。所以寻找的目标是一个递减序列之后的递增。由于积水量只有在递增时才能计算，而计算又可能需要用到递减序列中的多个bar。因此必须将递减序列cache起来。这里使用stack。为了便于面积计算中宽度的计算，stack存放的不是递减序列bar的高度，而是每个bar的坐标。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public: int trap(int A[], int n) { if(n<3) return 0; stack<int> s; s.push(0); int water = 0; for(int i=1; i<n; i++) { if(A[i]>A[s.top()]) { int bottom = A[s.top()]; s.pop(); while(!s.empty() && A[i]>=A[s.top()]) { water += (A[s.top()]-bottom)*(i-s.top()-1); bottom = A[s.top()]; s.pop(); } if(!s.empty()) water += (A[i]-bottom)*(i-s.top()-1); } s.push(i); } return water; } };

思路2：two pointers解法

对任意位置i，在i上的积水，由左右两边最高的bar：A[left] = max{A[j], j<i}, A[right] = max{A[j], j>i}决定。定义Hmin = min(A[left], A[right])，则积水量Si为：

Hmin <= A[i]时，Si = 0
Hmin > A[i]时，Si = Hmin - A[i]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int trap(int A[], int n) { if(n<3) return 0; vector<int> leftHeight(n,0); vector<int> rightHeight(n,0); int water = 0; for(int i=1; i<n; i++) leftHeight[i] = max(leftHeight[i-1], A[i-1]); for(int i=n-2; i>=0; i--) { rightHeight[i] = max(rightHeight[i+1], A[i+1]); int minHeight = min(leftHeight[i], rightHeight[i]); if(minHeight>A[i]) water += (minHeight - A[i]); } return water; } };