Description
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.
Example
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
思路
- 最开始用一个栈实现，16ms，思路有点复杂了
- 栈里存的是小于当前最大值的元素。比如最开始是0，然后当前最大值是0，遇到1后出栈，然后1入栈，然后存0，然后遇到2，全部出栈，2入栈。。在这个过程中计算存水量
- 思路2：借鉴11题的思路。
代码
- 用栈实现
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
if (len <= 2) return 0;
stack<int> Stack;
int res = 0, i = 0, smax = height[0], index = 0;
int sum = 0, tmp = 0, last = 0;
while (i < len){
if (Stack.empty() || height[i] < smax){
Stack.push(i);
i++;
continue;
}
else{
tmp = 0;
sum = 0;
while (!Stack.empty()){
tmp = Stack.top();
if (Stack.size() > 1)
sum += height[tmp];
Stack.pop();
}
smax = height[i];
index = i - tmp - 1;
res += min(height[i], height[tmp]) * index - sum;
}
}
if (Stack.empty()) return res;
last = Stack.top();
Stack.pop();
while (!Stack.empty()){
if (height[last] <= height[Stack.top()]){
last = Stack.top();
Stack.pop();
}
else{
tmp = -1;
sum = 0;
while (!Stack.empty() && height[Stack.top()] < height[last]){
tmp = Stack.top();
Stack.pop();
sum += height[tmp];
}
if (Stack.empty()) break;
tmp = Stack.top();
Stack.pop();
index = last - tmp - 1;
res += min(height[last], height[tmp]) * index - sum;
last = tmp;
}
}
return res;
}
};- 借鉴11题的思路，非常巧妙，找个例子顺着代码理一理就通了
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int left = 0;
int right = len - 1;
int sum = 0;
while (left < right)
{
int m = min(height[left], height[right]);
if (height[left] == m)
{
while (++left < right && height[left] < m)
sum += m - height[left];
}
else{
while (left < --right && height[right] < m)
sum += m - height[right];
}
}
return sum;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
