??????
??????830. 單調棧 - AcWing題庫
給定一個長度為?N?的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出??1?1。
輸入格式
第一行包含整數?N，表示數列長度。
第二行包含?N個整數，表示整數數列。
輸出格式
共一行，包含?N?個整數，其中第?i個數表示第 i?個數的左邊第一個比它小的數，如果不存在則輸出??1?1。
數據范圍
1≤N≤1051≤≤105
1≤數列中元素≤1091≤數列中元素≤109
輸入樣例：
5
3 4 2 7 5
輸出樣例：
-1 3 -1 2 2?
經典算法模板，單調棧，性質：找到左邊或右邊第一個大或小的數，通過模擬棧或者使用stl棧，保證棧中元素一直保持單調性，棧頂元素就是第一個比它小或大的元素
ac代碼
?
using namespace std;const int N = 100010;int stk[N], tt;int main() {int n;cin >> n;while (n -- ){int x;scanf("%d", &x);while (tt && stk[tt] >= x) tt -- ;if (!tt) printf("-1 ");else printf("%d ", stk[tt]);stk[ ++ tt] = x;}return 0; }
