跳转至

42 接雨水

接雨水的本质:对于下标 i,下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值,下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]

暴力解法

通过循环找出下标 i 两边的最大高度leftMax和rightMax,再求最小值,这个最小值就是下标 i 处的水能到达的最大高度

leftMax和rightMax计算过程包含height[i]

下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        for(int i = 0; i < n; i++){
            int leftMax = 0, rightMax = 0;
            // 记得leftMax包含height[i]
            for(int j = 0; j <= i; j++){
                leftMax = max(leftMax, height[j]);
            }
            // 记得rightMax包含height[i]
            for(int j = i; j < n; j++){
                rightMax = max(rightMax,height[j]);
            }
            if(leftMax < rightMax){
                res += leftMax - height[i];
            }
            else
                res += rightMax - height[i];
        }
        return res;
    }
};

时间复杂度:\(O(2n^2)\)

空间复杂度:\(O(n)\)

动态规划

在暴力解法的基础上分析,我们发现,每次从i左右两侧遍历寻找最高度需要\(O(n)\),这里面重复了很多次

我们干脆一次遍历使用数组记录leftMax[i]和rightMax[i]

  • leftMax[i]表示i左侧高度最大值
  • rightMax[i]表示i右侧高度最大值

观察代码你会发现,其实也就是将第二层for循环提到外面

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;
        // leftMax[i]表示i左侧高度最大值
        // rightMax[i]表示i右侧高度最大值
        int leftMax[n], rightMax[n];
        // 初始化
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        // 更新leftMax和rightMax
        for (int i = 1; i < n; i++) {
            // 记得leftMax包含height[i]
            leftMax[i] = max(leftMax[i - 1],height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            // 记得rightMax包含height[i]
            rightMax[i] = max(rightMax[i + 1],height[i]);
        }
        for (int i = 0; i < n; i++) {
            if (leftMax[i] < rightMax[i]) {
                res += leftMax[i] - height[i];
            } else
                res += rightMax[i] - height[i];
        }
        return res;
    }
};

时间复杂度:\(O(n)\)

空间复杂度:\(O(n)\)

单调栈法

单调栈特点:

  • 栈内记录下标
  • 单调递减栈
    • 栈底到栈顶,元素单调递减
    • 当遇到height[i] > height[stk.top()],需要弹出栈顶元素,此时大小关系有:
      1. height[i] > height[stk.top()]
      2. 弹出栈顶元素int idx = stk.top();
      3. height[stk.top()] >= height[idx],这里的stk.top()与第一步的stk.top()不同

从左到右遍历数组,遍历到下标 i 时,如果栈内至少有两个元素,记栈顶元素为 top,top 的下面一个元素是 left,则一定有 height[left]≥height[top]。如果 height[i]>height[top],则得到一个可以接雨水的区域

  • 该区域的宽度是 i−left−1
    • 当height[i]>height[top],我们找到了两侧最大值,分别为rightMax(height[i])和leftMax(height[left]),两侧之间的区域就是接雨水的区域
    • 由于接雨水区域不包括两侧最大值,因此width = i - left - 1
  • 高度是 min(height[left],height[i])−height[top]

根据宽度和高度即可计算得到该区域能接的雨水量。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> stk;
        int ans = 0;
        for(int i = 0; i < n; i++){
            // 这里注意用的是while 不是 if
            while(!stk.empty() && height[i] > height[stk.top()]){
                int idx = stk.top();
                stk.pop();
                // 记得判断边界条件
                if(stk.empty())
                    break;
                int left = stk.top();
                int minHeight = min(height[left], height[i]);
                ans += (minHeight - height[idx]) * (i - left - 1);
            }
            stk.push(i);
        }
        return ans;
    }
};

双指针法

暴力解法本质上就是比较两侧元素大小,因此可以采用同侧双指针法优化

本题中,我们比较的是两侧高度最大值的最小值,因此分为两步

  1. 记录两侧高度的最大值 -> 在指针移动过程中进行
  2. 对两侧高度最大值进行取最小值 -> min(leftMax, rightMax)

问题在于如何求解下标 i 处能接的雨水量,即使用双指针后,下标i如何表示

  • 双指针问题特性:left和right交替移动,最终遍历完整个数组,因此下标i实际上是移动的left和right
  • 我们得到最小值后,立即计算这一侧的雨水量
    • 如果leftMax < rightMax,那么计算res += leftMax - height[left];
    • 如果leftMax > rightMax,那么计算res += rightMax - height[right];
    • 这是因为,得到最小值后,我们会移动相应的指针。以leftMax < rightMax为例,假设当前left == 2,我们会更新left,之后我们不会再计算这个指针指向的height[2],因此计算雨水量使用leftMax - height[left]
  • 为什么leftMax < rightMax,移动left
    • 这是因为雨水量由最小值决定,如果移动rightMax,除非新的rightMax小于leftMax,否则对结果没有任何影响
    • 而rightMax是递增的,每次都只会取更大值,即rightMax = max(rightMax, height[right]),因此rightMax不可能小于leftMax
    • 因此我们移动最小值那一侧的指针
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int leftMax = height[left], rightMax = height[right];
        int res = 0;
        while(left < right){
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if(leftMax < rightMax){
                res += leftMax - height[left];
                left++;
            }
            else{
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
};

时间复杂度:\(O(n)\)

空间复杂度:\(O(1)\)

滑动窗口

滑动窗口算法可以用于解决一些字符串和数组问题,滑动窗口记录最大值、最小值、子串长度

例如:

  • 字符串匹配问题,例如 Leetcode 第 28 题和第 76 题;
  • 最长子串或子数组问题,例如 Leetcode 第 3 题、第 209 题和第 424 题;
  • 最小覆盖子串问题,例如 Leetcode 第 76 题;
  • 字符串排列问题,例如 Leetcode 第 567 题;
  • 求解字符串或数组中的一些性质,例如 Leetcode 第 438 题、第 567 题和第 1004 题等。