Leetcode42接雨水
- 题解1:正反两扫(Simple and effect)
- 题解2:DP
- 题解3:单调栈(单调栈存储的是下标,满足从栈底到栈顶的下标对应height的元素呈递减)
- 题解4:双指针(dp/前后扫 plus-math related)
给定
n
个非负整数表示每个宽度为
1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
- 1
<= n <=
2 * 104 - 0
<= height[i] <=
105
来源:力扣(LeetCode)题目链接
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解1:正反两扫(Simple and effect)
class Solution {
public:
int trap(vector<int>& height) {
int s = height.size();
if(1==s) return int(0);
int i=0, j=0;
int sum = 0;
while(i < s && j < s-1){
if(height[++j] >= height[i]){
sum += height[i]*(j-i-1);
for(int x=i+1; x<j; x++){
sum -= height[x];
}
i = j;
}
}
if(j == s-1 && i != j){
int n = j;
while(j > i && n > i){
if(height[--n] >= height[j]){
sum += height[j]*(j-n-1);
for(int x=j-1; x>n; x--){
sum -= height[x];
}
j = n;
}
}
}
return sum;
}
};
题解2:DP
class Solution {
public:
int trap(vector<int>& height) {
const int s = height.size();
if(1==s) return int(0);
int leftMax[s];
leftMax[0] = height[0];
int rightMax[s];
rightMax[s-1] = height[s-1];
int sum = 0;
for(int i=1; i<s; i++){
leftMax[i] = max(leftMax[i-1], height[i]);
}
for(int i=s-2; i>=0; i--){
rightMax[i] = max(rightMax[i+1], height[i]);
}
for(int i=0; i<s; i++){
sum += min(leftMax[i], rightMax[i])-height[i];
}
return sum;
}
};
题解3:单调栈(单调栈存储的是下标,满足从栈底到栈顶的下标对应height的元素呈递减)
class Solution {
public:
int trap(vector<int>& height) {
const int s = height.size();
if(1==s) return int(0);
stack<int> sk;
int sum(0);
for(int i=0; i<s; i++){
while(!sk.empty() && height[i] >= height[sk.top()]){
auto m = sk.top();
sk.pop();
if(sk.empty()) break;
sum += (min(height[i], height[sk.top()]) - height[m])*(i-sk.top()-1);
}
sk.push(i);
}
return sum;
}
};
题解4:双指针(dp/前后扫 plus-math related)
class Solution {
public:
int trap(vector<int>& height) {
const int s = height.size();
if(1==s) return int(0);
int left(0), right(s-1);
int leftMax = 0;
int rightMax = 0;
int sum = 0;
while(left < right){
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);
if(leftMax < rightMax){
sum += leftMax-height[left];
left++;
}else{
sum += rightMax-height[right];
right--;
}
}
return sum;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)