acwing 830 單調棧

題面

題解

1. 先考慮暴力做法 ,看資料範圍1e5 ，O（n2）肯定過不了 ，那麼我們考慮優化内層循環

for(int i=0;i<n;i++){   //循環每一個數
        for(int j=i-1;j>=0;j--){   //從這個數的左邊開始往前找
            if(a[i]>a[j]){
                break;
            }
        }
    }
           

1. （重點）題中要求數左邊離它最近且比它小的數，我們可以知道，如果ai >= a j ,那麼對于aj 後邊的數，肯定是不會用到 ai 的，因為有aj的存在，最優解一定是aj
2. 是以我們可以用一個單調棧（代碼是用數組模拟棧）來維護，這個單調棧遞增，從前往後周遊的時候，如果棧頂元素小于目前值x，那麼這個值一定是離它最近小于它的點，如果是大于等于，那麼就删除棧頂元素，繼續比較直到小于或者棧為空，輸出對應的答案，然後将這個x加入棧中（仍然是一個單調遞增的棧），繼續周遊

代碼

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n;
int stk[N], tt;

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt--;
        if (tt) cout << stk[tt] << " ";
        else cout << -1 << " ";
        stk[++tt] = x;
    }
    return 0;
}