leetcode 42. 接雨水

2023.8.29

         本题可以用双指针做，求出每一列能盛的雨水，再相加即可。不过暴力法会超时，需要优化。

双指针（暴力）：

class Solution {
public:int trap(vector<int>& height) {int ans = 0;for(int i=1; i<height.size()-1; i++){int max_rheight = height[i]; //记录当前柱子右边的最高柱子int max_lheight = height[i]; //记录当前柱子左边的最高柱子for(int r=i+1; r<height.size(); r++){max_rheight = max(max_rheight,height[r]);}for(int l=i-1; l>=0; l--){max_lheight = max(max_lheight,height[l]);}ans += max(0 , min(max_rheight,max_lheight)-height[i]);}return ans;}
};

双指针（优化）：

        上面双指针暴力法每次遍历都需要求一次当前柱子左右两侧的最高柱子，这样有重复，自然会超时。 优化办法是设置两个数组left和right，分别存储每一个柱子的左侧最高柱子，及右侧最高柱子，这样子就不用重复遍历了。 代码如下：

class Solution {
public:int trap(vector<int>& height) {//求出当前柱子的左侧最高柱子以及右侧最高柱子，保存在两数组中。vector<int> left(height.size());vector<int> right(height.size());int max_lheight = height[0];int max_rheight = height[height.size()-1];for(int i=1; i<left.size()-1; i++){left[i] = max_lheight;max_lheight = max(max_lheight,height[i]);}for(int i=right.size()-2; i>=1; i--){right[i] = max_rheight;max_rheight = max(max_rheight,height[i]);}//遍历每一列求出最大雨水int ans = 0;for(int i=1; i<height.size()-1; i++){ans += max(0 , min(left[i],right[i])-height[i]);}return ans;}
};