单调栈例题：单调栈

我们先来看题目描述：

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

输入格式：

第一行包含整数 N ，表示数列长度。第二行包含 N 个整数，表示整数数列。

输出格式：

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

数据范围 ：

1 ≤ N ≤ 10^5

1 ≤ 数列中的元素 ≤ 10^9

输入样例：

5 3 4 2 7 5

输出样例：

-1 3 -1 2 2

解题代码：

#include<bits/stdc++.h> using namespace std; int a[100010],res[100010],n; stack<int>S; stack<int>id; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } memset(res,-1,sizeof(res)); for(int i=n;i>=1;i--){ while(!S.empty()&&a[i]<S.top()){ res[id.top()]=a[i]; S.pop(); id.pop(); } S.push(a[i]); id.push(i); } for(int i=1;i<=n;i++){ printf("%d ",res[i]); } }