Bad Hair Day POJ – 3250(初识单调栈)

题目链接:https://cn.vjudge.net/problem/POJ-3250#author=Tiw_Air_OAO

关于单调栈:https://blog.csdn.net/zuzhiang/article/details/78134247

就是维护一个递增/递减的栈,操作也很简单,
假如要维护一个单调递增栈,在元素入栈的时候先把栈中比当前元素小的元素出栈,再把它入栈,这样就可以保证栈中元素的单调递增。

代码

#include <iostream>
#include <stack>
using namespace std;

struct node
{
    int data,id;
};

stack<node>q;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    node d;
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>d.data;
        d.id=i;
        if(q.empty())
        {
            q.push(d);
        }
        else
        {
            while(!q.empty()&&q.top().data<=d.data)
            {
                ans+=(i-q.top().id-1);
                q.pop();
            }
            q.push(d);
        }
    }
    while(!q.empty())
    {
        ans+=(n-q.top().id-1);
        q.pop();
    }
    cout<<ans<<endl;
    return 0;
}

1 thought on “Bad Hair Day POJ – 3250(初识单调栈)”

发表评论

电子邮件地址不会被公开。 必填项已用*标注