題意#
題目給定長度為 \( n \) 的整數陣列。
針對陣列中的每個數字，需要在其「左側」尋找距離最近且數值「嚴格小於」該數字的元素。
如果找到，輸出該元素的位置（1-indexed）；若無較小元素，則輸出 0。
思路#
此為經典的「單調棧（Monotonic Stack）」題型。
單調棧透過維護一個候選名單，能以 \(\mathcal{O}(N)\) 解決尋找「最近較大/較小元素」的問題。
從左到右掃描陣列，使用一個堆疊（Stack）存放看過的元素位置。
當處理新數字時，檢查 Stack 頂端元素：
若頂端元素大於或等於當前數字，代表該元素數值較大且距離較遠。
由於當前數字是更小、更近的候選者，未來的數字一定會優先選擇當前數字。因此，Stack 頂端的舊數字已失去競爭力，將其移出（pop）。
持續移除直到 Stack 頂端元素小於當前數字。
此時頂端元素即為左側最近較小的數字，記錄其位置後，將當前數字的位置推入 Stack 成為未來的候選者。
過程中每個數字最多進出 Stack 一次，整體效能為 \(\mathcal{O}(N)\)。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
vector<int> v(n);
for (auto &i : v) cin >> i;
// sk 用來存放數字所在的位置（採用 1-based index 方便處理）
stack<int> sk;
for (auto &i : v) {
// 當 Stack 頂端數字大於等於當前數字時，將其淘汰
while (sk.size() && i <= v[sk.top()]) sk.pop();
// Stack 頂端即為符合條件的答案；若為空代表無較小數字，輸出 0
cout << (sk.size() ? sk.top()+1 : 0) << ' ';
// 將自己的位置推入 Stack 中，成為未來的候選人
// &i-v.data() 是利用指標運算快速取得當前元素在 vector 中的 0-based 索引
sk.push(&i-v.data());
}
}
