单调栈:
用于解决求出距离当前值最近的满足某个性质的值
1 给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。 2 3 输入格式 4 第一行包含整数N,表示数列长度。 5 6 第二行包含N个整数,表示整数数列。 7 8 输出格式 9 共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。 10 11 数据范围 12 1≤N≤105 13 1≤数列中元素≤109 14 输入样例: 15 5 16 3 4 2 7 5 17 输出样例: 18 -1 3 -1 2 2 19 20 21 ######################## 22 23 #include <iostream> 24 25 using namespace std; 26 27 const int N = 1e5+10; 28 29 int arr[N]; 30 int stk[N], top = -1; 31 32 int main(){ 33 int n; 34 cin >> n; 35 for(int i = 0;i < n;++i){ 36 cin >> arr[i]; 37 } 38 for(int i = 0;i < n;++i){ 39 //stack存下标和值都可以 40 while(top >= 0 && stk[top] >= arr[i])--top; 41 if(top >= 0)printf("%d ",stk[top]); 42 else printf("-1 "); 43 stk[++top] = arr[i]; 44 } 45 return 0; 46 }
单调队列:
end