leetcode42：接雨水

题目链接

leetcode

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

/*
    暴力解法，TLE
    对于每个柱子 i，遍历数组分别找到左边和右边最高的柱子，计算雨水量。

    时间复杂度：O(n^2)
        其中 n 是数组的长度。遍历数组三次。
    空间复杂度：O(1) 
*/
class Solution_0 {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int res = 0;

        for (int i = 0; i < n-1; i++) {
            int l_max = 0, r_max = 0;

            // 找到右边最高的柱子
            for (int j = i; j < n; j++) {
                r_max = max(r_max, height[j]);
            }
            // 找到左边最高的柱子
            for (int j = i; j >= 0; j--) {
                l_max = max(l_max, height[j]);
            }
            // 更新当前的雨水量
            res += min(l_max, r_max) - height[i];
        }

        return res;
    }
};

/*
    观察整个图形，对水的面积按列进行拆解。
    每个矩形条上方接到水的高度，是由它左边矩形和右边矩形决定的。

    数组 l_max 和 r_max
        l_max[i] 表⽰位置 i 左边最⾼的柱子高度，
        r_max[i] 表⽰位置 i 右边最⾼的柱子高度。
    预先把这两个数组计算好，避免重复计算。
    最后统计答案：
        第 i 个矩形条，接到雨水量为 min(l_max[i], r_max[i]) - height[i]。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组三次。
    空间复杂度：O(n) 
        两个数组分别记录每个位置左边和右边的高度。
*/
class Solution_1 {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }
        
        int n = height.size();
        vector<int> l_max(n), r_max(n);
        // 初始化
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];

        // 从左向右计算 l_max
        for (int i = 1; i < n; i++) {
            l_max[i] = max(l_max[i-1], height[i]);
        }
        // 从右向左计算 r_max
        for (int i = n-2; i >= 0; i--) {
            r_max[i] = max(r_max[i+1], height[i]);
        }
        // 计算雨水量
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += min(l_max[i], r_max[i]) - height[i];
        }
        
        return res;
    }
};

/*
    一个位置的储水量取决于左右高度中较低的。
    这次不使用备忘录提前计算，双指针一边走一边算，节省空间复杂度。

    初始化时，将左右指针放在最左边、最右边，每次移动高度较低的指针（瓶颈）。
    若移动后的高度变大，则当前位置不能存水，更新边界高度；
    若移动后的高度变小，则当前位置可以存水，计算存水量并更新答案。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组一次。
    空间复杂度：O(1)
        使用了几个变量。
*/
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

        int l = 0, r = height.size()-1;
        int l_max = 0, r_max = 0;
        int res = 0;
        
        while (l <= r) {
            l_max = max(l_max, height[l]);
            r_max = max(r_max, height[r]);

            // 计算雨水量
            if (l_max < r_max) {
                res += l_max - height[l];
                l++;
            } else {
                res += r_max - height[r];
                r--;
            }
        }

        return res;
    }
};

/*
    维护一个存储柱子索引的栈，这个栈中的索引对应的柱子高度保持单调递减。
    当遇到一个比栈顶柱子高的柱子时，就找到了一个可以积水的"凹陷"区域。

    遍历数组，对于每个柱子：
        若栈不为空且当前柱子高度大于栈顶柱子高度，则弹出栈顶柱子并计算其接水量。
        否则，将当前柱子的索引入栈。
    计算接水量：
        stk.top()、top 与 i 三个位置构成一个 U 型，
        其中 top 位置代表 U 型的底部，计算出该 U 型可以接水的面积。

    时间复杂度：O(n)
        其中 n 是数组的长度。遍历数组一次。
    空间复杂度：O(n)
        存储单调栈的空间 O(n)。
*/
class Solution_3 {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

        int res = 0;
        stack<int> stk;

        for (int i = 0; i < height.size(); i++) {
            // 当前柱子高度大于栈顶元素时，计算能接的雨水量
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top(); stk.pop();
                // 若栈为空，则说明没有左边界，不能形成凹槽接水
                if (stk.empty()) {
                    break;
                }
                
                int w = i - stk.top() - 1;
                int h = min(height[i], height[stk.top()]) - height[top];
                res += w*h;
            }
            stk.push(i);
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> height_cases = {
        {0,1,0,2,1,0,1,3,2,1,2,1},
        {4,2,0,3,2,5}
    };

    for (auto& nums : height_cases) {
        int result = solution.trap(nums);

        cout << "Input: ";
        printArray(nums);
        cout << "Input: " << result << endl;
    }
    
    return 0;
}