单调栈
例题:
给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2
解题思路
用单调递增栈维护,当比栈顶大时,直接输出栈顶元素,并入栈;
比栈顶元素小时,则出栈,直到比栈顶元素小,重复上一步,或者为空输出-1,入栈;
using namespace std; const int N = 1E5 + 10; int b[N],top = 0; bool isempty(){ if(top == 0)return true; return false; } void push_stack(int x){ b[top++] = x; } int main(){ int a[N],n; scanf("%d",&n); for(int i = 0; i < n ; i++)scanf("%d",&a[i]); for(int i = 0; i < n ; i++){ if(isempty()){ printf("-1 "); push_stack(a[i]); } else{ while(top && a[i] <= b[top - 1])top--; if(isempty()){ printf("-1 "); push_stack(a[i]); } else{ printf("%d ",b[top - 1]); push_stack(a[i]); } } } return 0; }
|