IT源码网

接雨水

luoye 2020年10月22日 编程语言 659 0

给定 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

解:

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。

class Solution { 
public: 
    int trap(vector<int>& height) { 
        stack<int> sta_int; 
        int index =0; 
        int area=0; 
        while(index<height.size()) 
        { 
            //当前元素大于栈顶,形成了两端闭环的右端条件 
            //而根据下面循环条件,在栈中栈顶的都是比栈底的小 
            //所以两边的闭环条件都形成了 
            while(!sta_int.empty()&&height[index]>height[sta_int.top()]) 
            { 
                int i_level=sta_int.top(); 
                sta_int.pop(); 
                //此时栈中为空,说明前面没有比i_level大的了 
                if(sta_int.empty()) 
                { 
                    break; 
                } 
                //此时的sta_int的top,实际做的是左边的高度 
                int distance =index-sta_int.top()-1; 
                int h=min(height[index],height[sta_int.top()])- height[i_level]; 
                //面积是阶梯计算的 
                area+=h*distance; 
            } 
            sta_int.push(index++); 
        } 
        return area; 
    } 
};

 

评论关闭
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!