Leetcode—42. 接雨水【困难】
2024每日刷题（112）
Leetcode—42. 接雨水
空间复杂度为O(n)的算法思想
实现代码
class Solution {
public:int trap(vector<int>& height) {int ans = 0;int n = height.size();vector<int> l(n);vector<int> r(n);for(int i = 0; i < n; i++) {l[i] = i == 0 ? height[i] : max(height[i], l[i - 1]);}for(int i = n - 1; i >= 0; i--) {r[i] = i == n - 1 ? height[i] : max(height[i], r[i + 1]);}for(int i = 0; i < n; i++) {ans += min(l[i], r[i]) - height[i];}return ans;}
};
运行结果
空间复杂度为O(1)的算法思想
实现代码
class Solution {
public:int trap(vector<int>& height) {int ans = 0;int n = height.size();int l = 0, r = n - 1;int premax = 0, sufmax = 0;while(l < r) {premax = max(premax, height[l]);sufmax = max(sufmax, height[r]);if(premax < sufmax) {ans += premax - height[l];l++;} else {ans += sufmax - height[r];r--;}}return ans;}
};
运行结果
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！