【LeetCode 42】接雨水
LeetCode 42
2023-09-14 09:03:43 时间
【题解】
考虑每个位置它最后能接多少单位的水。 显然就是这个min(位置左边最高的位置,位置右边最高的位置)-当前这个位置的高度。 这就是这个位置最后水上涨的高度。 两个边界注意是不会储水的(都会掉到左边或者右边的边界外去). 每个位置左边最高的位置可以用DP很容易搞出来【代码】
class Solution {
public:
const int N = 1e5;
int trap(vector<int>& height) {
int maleft[N+10],maright[N+10];
memset(maleft,0,sizeof(maleft));memset(maright,0,sizeof(maright));
int n = height.size();
for (int i = 0;i < n;i++){
if (i>0) maleft[i] = maleft[i-1];
maleft[i] = max(maleft[i],height[i]);
}
for (int i = n-1;i>=0;i--){
if (i<n-1) maright[i] = maright[i+1];
maright[i] = max(maright[i],height[i]);
}
int ans = 0;
for (int i = 1;i < n-1;i++){
//cout<<maleft[i]<<" "<<maright[i]<<endl;
ans = ans + min(maright[i],maleft[i])-height[i];
}
return ans;
}
};
相关文章
- leetcode 191 二进制中1的个数 js 实现
- LeetCode笔记:Biweekly Contest 85
- leetcode 792_单词编码
- Leetcode题目037-解数独
- LeetCode 7. 整数反转
- leetcode 20. 有效的括号 js实现
- LeetCode 第3题 无重复字符的最长子串(小白详解)
- JavaScript刷LeetCode拿offer-链表篇
- leetcode刷题(125)——931. 下降路径最小和
- LeetCode题解——哈希表篇
- js刷leetcode动态规划(图文视频讲解)
- JavaScript刷LeetCode拿offer-js版字典
- 【动态规划】LeetCode 题解:494-目标和
- 前端工程师leetcode算法面试必备-二分搜索算法(下)_2023-03-15
- leetcode每日一题:字符串压缩
- C 语言的 LeetCode 30 天挑战 第3部分,共10部分
- Leetcode(153) Find Minimum in Rotated Sorted Array详解编程语言