单调栈理解加应用

提示：这里的栈是用数组模拟实现的栈，算法竞赛中长用到的栈的表示方法（用空间来换取时间---->快，快，快）。

• 单调栈的理解+应用：
• 一、数组怎么样模拟栈
• • 1.栈（一种能够使数组先进后出的结构）
  • 2.数组模拟栈
• 二、单调栈的理解
• 三、单调栈的应用
• • 例子：输出每个数左边第一个比它小的数
• 总结

指针实现：可以通过前插法或者后插法来生成栈。（本文将不会讲到，想要了解的可以看下面链接文章）。
栈及栈的基本操作

数组模拟实现：通过数组这个简单常用的数组层出结构实现栈同样的功能。

说明： 没有数据在存入栈中，要说明这个数组的两个属性：数据的值，数据的位置，数组是怎么样的实现对上面两个属性的描述的呢？

首先：我们先定义两个数组 e[N]， ne[N]。
e[N]：记录数据的值，例如e[1]=1，表示在1位置上的数据值为1。
ne[N]：记录数据的位置，例如ne[1]=2，表示1这个节点连接上2这个节点。

类似指针生成栈，数组模拟栈也有栈初始化，栈生成创建，增删改查。
代码理解实现
下面展示一些 内联代码片。

栈的初始化，为了更好的维护栈
void init_stack(){
	//idx表示栈的“指针”的起始位置。
	int e[100010],ne[100010],idx=0;
}

首先定义一下栈的操作：
实现一个栈，栈初始为空，支持四种操作：

push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。

//栈的增删改差
#include 
using namespace std;
int main()
{
    string a;
    int s,n,tt=0,b[100005];
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>a;
    if(a=="push")
    {cin>>s;
    b[++tt]=s;}
    if(a=="pop")
    tt--;
    if(a=="empty")
    if(tt==0)
    cout<<"YES"< 
二、单调栈的理解 
单调栈： 顾名思义嘛，具有单调性质的栈。
 类似数组，一个单调的数组，可以方便许多操作，比如：查找数组中的最大的、最小值，数组模拟的栈同样具有类似的性质。
 
不同于数组：栈的不能按照索引来取元素，但是可以很快的增加删除一个或多个元素。
 怎么样实现单调栈呢？
 实现思想：
 我们可以借用约瑟夫环的实现思想来实现一个单调栈。--------------------->循环插入，逐一判断。
 
下面展示一些 内联代码片。
 
int tt=0,stk[N];
int data[N]={......};
//data[N]需要维护的栈的元素值
for(int i=0;i=x) tt--;
	stk[++tt]=data[i];
	/保证栈是稳定的，元素可以循环稳定插入
	if(i==N) i=0,Na=N-stk.length()+1;
}
 
排难解惑区
 1，为什么判断条件stk[tt]>=x ?
 答：tt标记的是栈顶元素，当栈顶元素大于即将插入的元素，此时不能保证栈为一个严格单调增的栈，故将栈顶的元素剔除。
 
2，为什么执行代码：stk[++tt]=data[i];
 答：在维护栈后，栈开始为空，我们要将符合条件的，也就是严格单调增的数据添加到的我们的栈中。
 3，为什么执行代码：
 if(i==N) i=0,Na=Nstk.length()+1;
 答：维护站的稳定，数据可以循环插入。
 
单调栈完整实现代码：
int tt=0,stk[N];
int data[N]={data01...};
for(int i=0;i=x) tt--;
	stk[++tt]=data[i];
	if(i==N) i=0,Na=N-stk.length()+1;
}
 
三、单调栈的应用 
例子：输出每个数左边第一个比它小的数 
题目简单描述
 给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
 输入格式
 第一行包含整数 N，表示数列长度。
 第二行包含 N个整数，表示整数数列。
 
大家可以简单的思考一下这个题目用单调栈怎么样解答：
 
 
解答代码如下：
 
#include 

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[ ++ tt] = x;
    }

    return 0;
}

 
显然这个题目暴力求解比较简单：
 朴素做法：先将数据加入数组，在将数组排序后输出，对应左边的元素，即可。
 显然，因为要用到排序算法，所以时间复杂度最好也是比O(n)大，无论是快排，还是桶排序等。
 
总结 
数组模拟栈是是实现的数据存储结构很多，它们都具有处理数据快的特点，可以理解为用时间换空间（对于很多数据量来讲，少量数据时两者差距很小）。
 
小编：薇薇的憨宝
 图像：