单调栈

裸题:直方图中最大的矩形

解题思路

用单调栈求解最大矩形。

操作流程

初始化所有元素的宽度为1
1.每一次入栈一个元素
2.如果前面有比这个元素更高的元素,就将其弹出(由于前面的都是单调递增的,所以如果前面一个元素比这个元素矮或持平就不用再往前遍历了),并将这个元素的宽度加一。并且边弹出边计算最大矩形面积(由于弹出顺序是从后往前弹出,所以弹出序列是单调递减的,于是记录答案是只需要ans=max(ans,所有弹出的宽度之和*当前元素的高度)。
3.所有元素加入之后,需要将队列清空。清空时同第二步第二句话。

我们来举一个例子

现在有一个直方图,如下图所示,每一个“#”都代表一个方块。我们来模拟一边单调栈的解法。

      #
#     #     #
# # # #   # #
# # # # # # #
# # # # # # #
# # # # # # #

宽度1 1 1 1 1 1 1

每一列的宽度都初始化为1
现在第一列是五个,将其加入栈,由于前面没有比它更高的一列,所以不需要弹出前面任何一列。
第二列是四个,由于第一列比它高,所以我们将第五列弹出,弹出的同时,记录弹出时的最大方块面积,并将第二列的宽度加一。
ans变为5
变为了下图:

    #
    #     #
# # #   # #
# # # # # #
# # # # # #
# # # # # #

宽度2 1 1 1 1 1

第三列是四个,前面没有比它更高的列列,同第一列,直接加入即可。

    #
    #     #
# # #   # #
# # # # # #
# # # # # #
# # # # # #

宽度2 1 1 1 1 1

第四列同第一列,直接加入即可。

    #
    #     #
# # #   # #
# # # # # #
# # # # # #
# # # # # #

宽度2 1 1 1 1 1

第五列是三个,加入队列。由于前面一列比它高,所以将前面一列弹出,ans=max(ans,15)。发现再前面一列也比它高,ans=max(ans,(1+1)4)。再前面一列也比它高,ans=max(ans,(1+1+2)*4)。最后将第五列的宽度更新为1+4=5。

    #
  # #
# # #
# # #
# # #

宽度5 1 1

后面两列由于都比前面所有的要高或持平,所以只需要加入即可

再全部遍历完之后,我们要将所有所剩元素弹出栈。

弹出最后一列时:ans=max(ans,1*5)
弹出倒数第二列时:ans=max(ans,(1+1)*4)
弹出倒数第三列时:ans=max(ans,(5+1+1)*3)

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int width,height;
};
int n;
stack<node> s;
long long h[100005];
long long ans;
int main(){
    while(cin>>n){
        memset(h,0,sizeof(h));
        ans=0;
        
        if(n==0){
            return 0;
        }
        for(int i=1;i<=n;i++){
            cin>>h[i];
        }
        node tmp;
        for(int i=1;i<=n;i++){
            if(s.empty()||h[i]>=s.top().height){
                tmp.width=1;
                tmp.height=h[i];
                s.push(tmp);
            }else{
                long long w=0;
                while(!s.empty()&&s.top().height>h[i]){
                    w+=s.top().width;
                    ans=max(ans,w*s.top().height);
                    s.pop();
                }
                tmp.width=w+1;
                tmp.height=h[i];
                s.push(tmp);
            }
        }
        long long w=0;
        while(!s.empty()){
            w+=s.top().width;
            ans=max(ans,w*s.top().height);
            s.pop();
        }
        cout<<ans<<endl;
    }
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/289/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者