CSES Nearest Smaller Values

一樣是單調stack的方法,

我們會維護一個遞增stack, 假設當前的值比stack最上層還要大, 就pop出去

直到找到一個比當前值還要小的值, 我們即可停止並且把這個值給標出來

算是lc 84的medium版

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    int n;
    std::cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    stack<int> st;
    vector<int> res(n, 0);
    for (int i = 0; i < n; i++) {
        if (st.empty() || arr[st.top()] < arr[i]) {
            res[i] = st.empty() ? 0 : st.top() + 1;
            st.push(i);
        } else {
            st.pop();
            i--;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << " ";
    }
    return 0;
}

時間複雜度為O(N)