LeetCode 289 接雨水(单调栈)

题目链接：接雨水

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路

用单调栈的思路，维护一个递减的单调栈，当不满足递减条件的时候，每弹出一个元素，就计算出这一块区域能接的水量，最后的和就是答案，复杂度为$O(n)$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    int trap(vector<int> &height)
    {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++)
        {
            while (!st.empty() && height[i] > height[st.top()])
            {
                int cur = height[st.top()];
                st.pop();
                int l = st.empty() ? -1 : st.top();
                ans += (l == -1) ? 0 : (min(height[l], height[i]) - cur) * (i - l - 1);
            }
            st.push(i);
        }
        return ans;
    }
};

最后修改于 2020-04-06

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。