leetcode42.接雨水

Posted on | In |
Words count in article: 249 | Reading time ≈ 1

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

示例：

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

分析：

1
单调栈：获取当前位置左右比他大的

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> skt;

        int res = 0;
        for (int i = 0;i < n;i ++) {
            while (!skt.empty() && height[skt.top()] < height[i]) {
                auto t = skt.top(); // i 为t右边第一个比他大的
                skt.pop();
                // 此时栈顶为左边第一个比他大的

                if (skt.empty()) break;
                res += (i - skt.top() - 1) * (min(height[i], height[skt.top()]) - height[t]);
            }
            skt.push(i);
        }


        return res;
    }
};

[原题链接](42. 接雨水 - 力扣（Leetcode）)

0%