[AcWing]830. 单调栈

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 -1

输入格式

第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式

共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 -1

数据范围

1 < N < 10^5
1 < 数列中元素 < 10^9

输入样例:

1
2
5
3 4 2 7 5

输出样例:

1
-1 3 -1 2 2

算法思想

给定一个序列,求每一个数的左边离它最近的小于等于大于等于它的数是什么。
单调栈需要维护一个单调的栈

注意:插入元素时需要与栈顶元素比较,以单调增为例子
更小则取而代之全部,否则,正常入栈

  1. 筛选操作:先保证栈顶元素就是新插入元素离得最近且最小的元素
  2. 输出操作:输出离x最近且最小的元素,如果没有就输出-1
  3. 入栈操作:x入栈,栈从数组下标1开始使用

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

const int N = 1000010;

int main(){

int n;
cin >> n;

int stk[N], tt = 0;

while(n --){
int x; cin >> x;

// 维护栈,单调递增
// 单调栈不为空且压栈元素x比栈顶元素小,则删除它们
while(tt && x <= stk[tt]) tt--;

// 单调栈顶剩下的总是离x最近的,比x小的数
// 单调栈里面还有元素
if(tt) cout << stk[tt] << " ";
else cout << "-1" << " ";

stk[++tt] = x;
}

return 0;
}