問題描述

給定一個包含 $n$ 整數的陣列，對於陣列中的每個位置，找出左邊最近數值較小的位置

單調性

指的是一個值隨著某個變數的增減，其變化趨勢只會持續增加或持續減少，不會反覆震盪。

常見題型為從某個方向找最近滿足條件的元素。

練習題

連結：https://cses.fi/problemset/task/1645/

可以使用 單調性 來解，找左邊最近且比較小的值，我們可以維護一個遞增的 stack （top 是最大的），只要它的值大於等於目前處理的 $arr[i]$ 就會不斷「彈出堆疊頂端」的元素。因為目前的 $arr[i]$ 比頂端還小而且還更後面，後面的數字在找左邊最近較小值時，一定會先找到 $arr[i]$。

時間複雜度 $O(n)$

完整程式碼

include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int arr[200005];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && arr[st.top()] >= arr[i]) {
            st.pop();
        }
        if (st.empty()) {
            cout << "0 ";
        } else {
            cout << st.top() << " ";
        }
        st.push(i);
    }
}