题目描述
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.
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!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
题意:给一个数组代表一个柱状图,请问这个柱状图最多能盛多少水。
算法1
(两趟扫描) $O(n^2)$
题解1:我们知道对于每一个柱子,它上方能盛多少水,取决于左右两边的高度最大值的最小值。所以我们可以先使用两遍扫描(动态规划)求出每个位置左边的最大值和右边的最大值(包括当前柱子)。再使用一遍扫描求出每个柱子能盛多少水。
int trap(vector<int>& height) {
int n = height.size(),res = 0;
if(n == 0) return 0;
int f[n] = {},g[n] = {};
f[0] = height[0];
for(int i = 1 ; i < n ; i ++)
f[i] = max(f[i - 1],height[i]);
g[n - 1] = height[n - 1];
for(int i = n - 2;i >= 0 ; i --)
g[i] = max(g[i + 1],height[i]);
for(int i = 0 ; i < n ; i ++)
res += min(f[i],g[i]) - height[i];
return res;
}
算法2
(双指针) $O(n)$
题解2:双指针算法。在上述动态规划中,我们分别从两边进行求解最大值,我们可以使用双指针来优化上述操作。初始时i = 0, j = n - 1
,left_max,right_max
分别代表i
指针左侧最大值,和j
指针右侧最大值。如果s[i] < s[j]
,说明此时阻碍当前盛水的是左侧,所以我们将i
指针右移。
int trap(vector<int>& height) {
int n = height.size(),i = 0, j = n - 1,res = 0;
if(n == 0) return 0;
int left_max = 0,right_max = 0;
while(i < j)
{
if(height[i] < height[j])
{
left_max = max(left_max,height[i]);
res += left_max - height[i];
i ++;
}else
{
right_max = max(right_max,height[j]);
res += right_max - height[j];
j --;
}
}
return res;
}
算法3
(单调栈) $O(n)$
题解3:单调栈。我们的做法是,遍历高度,如果此时栈为空,或者当前高度小于等于栈顶高度,则把当前高度的坐标压入栈,注意我们不直接把高度压入栈,而是把坐标压入栈,这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候,就说明有可能会有坑存在,可以装雨水。此时我们栈里至少有一个高度,如果只有一个的话,那么不能形成坑,我们直接跳过,如果多余一个的话,那么此时把栈顶元素取出来当作坑,新的栈顶元素就是左边界,当前高度是右边界,只要取二者较小的,减去坑的高度,长度就是右边界坐标减去左边界坐标再减1,二者相乘就是盛水量啦。
int trap(vector<int>& height) {
int n = height.size(),res = 0;
stack<int> st;
for(int i = 0 ; i < n ; i ++)
{
while(!st.empty() && height[i] > height[st.top()])
{
int top = st.top();
st.pop();
if(st.empty()) break;
int distance = i - st.top() - 1;
int bound_height = min(height[i],height[st.top()]) - height[top];
res += distance * bound_height;
}
st.push(i);
}
return res;
}