单调栈 寻找左区间最小的数及其对应的下标
给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
输入格式
第一行包含整数 N,表示数列长度。
第二行包含 N 个整数,表示整数数列。
输出格式
共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出 −1。
开一个数栈 和 下标栈 即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 100010;
int n;
int down[N], id[N], cnt;
int main (){
cin >> n;
stack<int> stk, idx;
for(int i = 0; i < n; i ++){
int x;
cin >> x;
while(!stk.empty() && stk.top() >= x) stk.pop(), idx.pop();
if(stk.empty()) down[i] = -1, id[i] = -1;
else{
down[i] = stk.top();
id[i] = idx.top();
}
stk.push(x);
idx.push(i);
}
for(int i = 0; i < n; i ++) cout << down[i] << ' ';
return 0;
}