(LeetCode 面试经典 150 题) 42. 接雨水 （单调栈）

思路：单调栈，时间复杂度0(n)。

下标为i的位置蓄水量，取决于其左右两侧的最高度p[i-1]、q[i+1]里的最小值min(p[i-1],q[i+1])。
蓄水量为：max(0,min(p[i-1],q[i+1])-height[i])

C++版本：

class Solution {
public:int trap(vector<int>& height) {int n=height.size();vector<int> p(n,0),q(n,0);p[0]=height[0];for(int i=1;i<n;i++){p[i]=max(p[i-1],height[i]);}q[n-1]=height[n-1];for(int i=n-2;i>=0;i--){q[i]=max(q[i+1],height[i]);}int sum=0;for(int i=1;i<n-1;i++){sum+=max(0,min(p[i-1],q[i+1])-height[i]);}return sum;}
};

JAVA版本：

class Solution {public int trap(int[] height) {int n=height.length;int[] p=new int[n];int[] q=new int[n];p[0]=height[0];for(int i=1;i<n;i++){p[i]=Math.max(p[i-1],height[i]);}q[n-1]=height[n-1];for(int i=n-2;i>=0;i--){q[i]=Math.max(q[i+1],height[i]);}int sum=0;for(int i=1;i<n-1;i++){sum+=Math.max(0,Math.min(p[i-1],q[i+1])-height[i]);}return sum;}
}

Go版本：

func trap(height []int) int {n:=len(height)p:=make([]int,n)q:=make([]int,n)p[0]=height[0]for i:=1;i<n;i++ {p[i]=max(height[i],p[i-1])}q[n-1]=height[n-1]for i:=n-2;i>=0;i-- {q[i]=max(q[i+1],height[i])}sum:=0for i:=1;i<n-1;i++ {sum+=max(0,min(p[i-1],q[i+1])-height[i])}return sum
}