每日一题:接雨水(LeetCode 42)

题目

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

输入: 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 个单位的雨水(蓝色部分表示雨水)。

解答

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() <= 2) return 0;

        stack<int> stk;
        int result = 0;

        for(int i = 0; i < height.size(); i++)
        {
            if(stk.empty())
            {
                stk.push(i);
            }
            else if(height[i] < height[stk.top()])
            {
                stk.push(i);
            }
            else if(height[i] == height[stk.top()])
            {
                stk.push(i);
            }
            else
            {
                while(!stk.empty() && height[i] > height[stk.top()])
                {
                    int bottom = stk.top();
                    stk.pop();
                    if(!stk.empty())
                    {
                        int h = min(height[stk.top()], height[i]) - height[bottom];
                        int w = i - stk.top() - 1; 
                        result += h*w;
                    }
                }
                stk.push(i);
            }
        }

        return result;
    }
};
扫描关注程序区

有任何问题,请联系邮箱:support@progdomain.com

THE END
分享
二维码
打赏
海报
每日一题:接雨水(LeetCode 42)
题目 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 输入: height = [0,1,0,2,1,0,1,3,2,1,2,1] 输……
<<上一篇
下一篇>>