算法基础学习——单调栈

Source

算法基础学习(复习)——单调栈

在这里插入图片描述

#前言
自己太久没做没使用单调栈做题目了,都有点搞忘了,所以今天写一篇单调栈的理解复习文章。

*##时间复杂度
在我们做题时,偶尔会遇到求一个数组中元素,左边或右边离它最近的最大或者最小值的问题。其实我们可以很容易想到一些时间复杂度为O(n^)的解题思路,但要想优化到O(n)的时间复杂度的话,我们就要使用单调栈来优化程序了。

###我的理解
单调栈,顾名思义,就是一个单调递增、单调递减的线性数据结构。
1.单调递增栈:就是从栈底到栈顶是从大到小的排列
2.单调递减栈:就是从栈底到栈顶是从小到大的排列
3.我们需要一个条件来维护这个栈的单调性

###代码模板

常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    
      
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

####具体讲解我们来看例题
给出项数为 n 的整数数列 a[1…n] 。
定义函数 f(i)代表数列中第 i 个元素之后第一个大于 a[i]的元素的下标,若不存在,则 f(i)=0。

输入格式
第一行一个正整数 n。
第二行 n个正整数 a [1…n] 。

输出格式
一行 n 个整数 f(1…n) 的值。

输入 #1

5
1 4 2 3 5

输出 #1

2 5 4 5 0

#####题解
因为是找到一个元素后面第一个大于它的数字的下标,即找到它右边第一个比它大的数的下标,我们可以先找到右边第一个比它大的数,再输出该数的下标。
第一个将原本栈内的数推出来的数字,就是右边第一个比它大的数字。最后我们要取这些数字的下标,就可以得到结果了。
我自己做了一个简易的动态图,第一次做,尽可能让大家理解。
在这里插入图片描述
上代码

//题目要求找到数组中第i个元素之后第一个大于ai的元素下标 (1,n) 
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6;
int a[N]; 
int stk[N],tt;//建立一个栈 ,存的是数组下标 
int ans[N];//用来存储答案 
int main()
{
    
      
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	cin >> a[i];
	for(int i = 0; i < n; i++)
	{
    
      
		//维护一个单调递减的单调栈 
		while(tt && a[stk[tt]] < a[i])//当栈不为空时,栈顶遇到了比它大的元素,将栈顶弹出 
		{
    
      
			ans[stk[tt]] = i + 1;//存储这个元素的下标+1 
			tt--;
		}
		stk[++tt] = i;//压栈 
	} 
	for(int i = 0; i < n; i++)
	cout << ans[i] << " ";
	return 0;
}

本人一见之得,谢谢大家阅读纠正!