学习:数据结构单调栈

单调栈,即栈内的元素是单调的,运用单调栈可以维护一些有顺序的序列,虽然单调栈理解起来容易,但是运用起来却不是那么容易

单调栈的概念及类型


单调栈内的元素一定是单调的,要么单调递增,要么单调递减。

如果单调栈维护单调递减序列:假如将要入栈的元素栈顶元素大,那么就将栈顶元素移出栈,然后继续判断将要入栈的元素栈顶元素的大小关系,循环移出将要入栈元素大的栈顶元素,直到将要入栈的元素栈顶元素小,才将将要入栈的元素移入栈。同理维护单调递增的元素也是如此

举个例子:将52841放入单调递增栈里面

  1.先将5入栈

  2.由于2比5小,将5出栈,再将2入栈

  3.由于8比2大,将8入栈

  4.由于4比8小,将8出栈,再将4入栈

  5.由于4比1大,2也比1大,将4,2依次出栈,再将1入栈

由于每个元素最多只有一次入栈和出栈的机会,所以用单调栈解决某些问题时,复杂度只有O(n)


单调栈的基础运用


题目大意:给定一组序列,针对序列中的每一个数,求出这个数左边第一个比它大的数的位置,若不存在,则为0;

思路:用单调递减栈维护每个数的位置,每次将一个数成功入栈时,入栈前栈顶位置即是入栈数左边第一大数的位置。成功入栈的条件是将要入栈的元素比栈顶位置元素值小)

注意:栈顶位置指栈顶那个数,假设栈顶位置为x,那么栈顶位置元素指原序列中第x个数。

例如序列为:52846

1.5的位置为1,将5的位置1入栈,且5左边第一大数位置0

2.2的位置为2,此时栈顶位置元素值为5,即2左边第一大数位置为1,将2的位置2入栈

3.8的位置为3,此时栈顶位置元素值为2,将栈顶位置2出栈,此时栈顶位置元素为5,继续将栈顶位置1出栈,然后将8的位置3入栈,即8的左边第一大位置为0

4.4的位置为4,此时栈顶位置元素值为8,即4左边第一大数位置为3,将4的位置4入栈

5.6的位置为5,此时栈顶位置元素值为4,将栈顶位置4出栈,此时栈顶位置元素为8,即6左边第一大位置为3

单调栈难得不在理解过程,而在于如何将单调栈应用于实际

#include <iostream>
#include <stack>
#define N 5
using namespace std;
stack<int> sta;
int main(){
    int num[N];
    int place[N];
    int i;
    sta.push(0);
    for(i=1;i<=N;i++){
        cin>>num[i];
        while(sta.size()>1){
            if(num[sta.top()]<=num[i])    sta.pop();
            else break;
        }
        place[i]=sta.top();
        sta.push(i);
    }    
    for(i=1;i<=N;i++)    cout<<place[i]<<" ";
} 
求序列中每个数左边第一大的位置

例题


1.牛客练习赛48----D-小w的基站网络:https://blog.csdn.net/weixin_43702895/article/details/95047578

2.2019牛客暑期多校训练营(第一场)----A-Equivalent Prefixes:https://blog.csdn.net/weixin_43702895/article/details/96444749

3.2019牛客暑期多校训练营(第二场)----H-Second Large Rectangle:https://blog.csdn.net/weixin_43702895/article/details/100164619

原文地址:https://www.cnblogs.com/qiyueliu/p/11156397.html