题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。 示例: 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
题解（暴力法）
这里的题解参考的是官方题解，自己太菜了! 首先使用的是暴力求解法，每个柱子能接的雨水量取决于它前面柱子最高的与后面柱子最高的，两者的较小值。这个想想应该就能明白。
代码
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
26
| /*
时间复杂度为：o(n^2)
空间复杂度为：o(1)
*/
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int l_max, r_max, ans = 0;
for(int i = 1; i < len - 1; ++i){
l_max = 0, r_max = 0;
for(int j = i; j >= 0; --j){//寻找左边柱子的最高值
if(height[j] > l_max){
l_max = height[j];
}
}
for(int j = i; j < len; ++j){//寻找右边柱子的最高值
if(height[j] > r_max){
r_max = height[j];
}
}
ans += min(l_max, r_max) - height[i];//接到的雨水量 = 能达到的高度 - height[i]。
}
return ans;
}
};
|
执行结果
题解（动态规划）
暴力法中第二重循环是用来寻找当前柱子左边的最高柱子和右边的最高柱子，我们是否可以维护一个数组来存储其左边最高柱子，另外一个数组存储其右边最高柱子?答案显然可以，只需从左向右扫描一次，从右向左扫描一次即可。相比暴力解法，多了两个数组来存储一些信息，但时间复杂度却从o(n^2)降为o(n)。
代码
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
26
27
28
29
30
31
32
|
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size(), res = 0;
vector<int>l_max_arr(len, 0);
vector<int>r_max_arr(len, 0);
for(int i = 0; i < len; ++i){
if(i == 0){
l_max_arr[i] = max(l_max_arr[0], height[i]);
}
else{
l_max_arr[i] = max(l_max_arr[i - 1], height[i]);
}
}
for(int i = len - 1; i >= 0; --i){
if(i == len - 1){
r_max_arr[i] = max(r_max_arr[len - 1], height[i]);
}
else{
r_max_arr[i] = max(r_max_arr[i + 1], height[i]);
}
}
for(int i = 1; i < len - 1; ++i){
res += (min(l_max_arr[i], r_max_arr[i]) - height[i]);
}
return res;
}
};
|
执行结果
题解（栈的应用）
有点巧妙，只是列出来，打死也想不出来。 我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到ans 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int trap(vector<int>& height)
{
int ans = 0, current = 0;
stack<int> st;
while (current < height.size()) {
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty())
break;
int distance = current - st.top() - 1;
int bounded_height = min(height[current], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
}
|
题解（双指针）
分左右两边计算，一次完成遍历。当height[left] < height[right]，两边最大中较小的只可能出现在左边，不可能在右边。两指针移动时，需不断更新l_max与r_max。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int left = 0, right = len - 1, res = 0;
int l_max = 0, r_max = 0;
while(left < right){
if(height[left] < height[right]){
l_max <= height[left]?l_max = height[left]:res += l_max - height[left];
++left;
}
else{
r_max <= height[right]?r_max = height[right]:res += r_max - height[right];
--right;
}
}
return res;
}
};
|
执行结果
