algo-aha

柱状图储水问题

• https://leetcode.com/problems/trapping-rain-water

方法一：某bar上的储水 = min(它左侧（含）最高的bar高，它右侧（含）最高的bar高) - 它自己的bar高

int trap(vector<int>& height) {
    if (height.empty()) return 0;
    // 某bar上的储水 = min(它左侧（含）最高的bar高，它右侧（含）最高的bar高) - 它自己的bar高
    const int N = height.size();
    vector<int> leftMax(N, 0);
    leftMax[0] = height[0];
    for (int i = 1; i < N; i++) {
        leftMax[i] = max(height[i], leftMax[i-1]);
    }
    vector<int> rightMax(N, 0);
    rightMax[N-1] = height[N-1];
    for (int i = N - 2; i >= 0; i--) {
        rightMax[i] = max(height[i], rightMax[i+1]);
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans += min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
}

方法二："波谷"的左右都比它高，贡献一个水层

int trap(vector<int>& height) {
    // 用栈找波谷
    int ans = 0;
    stack<int> stk;
    for (int i = 0; i < height.size(); i++) {
        while (!stk.empty() && height[i] > height[stk.top()]) {
            int valley = stk.top(); stk.pop();
            if (stk.empty()) break;
            int left = stk.top();
            // "波谷"的右i和左left都比它高，贡献一个水层
            int w = i - left - 1;
            int h = min(height[i], height[left]) - height[valley];
            ans += w * h;
        }
        stk.push(i);
    }
    return ans;
}

二维柱状图储水问题

• https://leetcode.com/problems/trapping-rain-water-ii

含水高度最小的先出队处理，看它的邻居。若邻居的含水高度更小，该邻居柱上可储水，储水量为高度差。

int trapRainWater(vector<vector<int>>& heightMap) {
    // 可视化解释：https://www.youtube.com/watch?v=cJayBq38VYw
    // 用优先队列的遍历算法
    if (heightMap.empty()) return 0;
    const int R = heightMap.size(), C = heightMap[0].size();
    // 队列元素int[3]: { row, col, heightWithWater }
    auto cmp = [](vector<int> &a, vector<int> &b) {
        return a[2] > b[2]; // 高度最小的先出队处理
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
    vector<vector<bool>> visited(R, vector<bool>(C, false));
    // 四条边先入队
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (r == 0 || r == R - 1 || c == 0 || c == C - 1) {
                pq.push({r, c, heightMap[r][c]});
                visited[r][c] = true;
            }
        }
    }

    int ans = 0;
    vector<vector<int>> dirs = { {-1, 0}, {0,1}, {1,0}, {0,-1} };
    while (!pq.empty()) {
        auto elem = pq.top();  pq.pop();
        int r = elem[0], c = elem[1], heightWithWater = elem[2];

        for (auto &dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]) continue;
            // 若邻居的高度更小，该邻居柱上可储水，储水量为高度差
            int diff = heightWithWater - heightMap[nr][nc];
            if (diff > 0) ans += diff;
            pq.push({nr, nc, max(heightWithWater, heightMap[nr][nc])});
            visited[nr][nc] = true;
        }            
    }
    return ans;
}