Codeforces 547B Mike and Feet：單調棧求各長度區間最大最小值

問題重述

給定 n 個數，對每個長度 x (1≤x≤n)，考慮所有長度為 x 的連續子區間，每個區間取最小值，求這些最小值中的最大值。

單調棧核心思想

對每個元素 a[i]，找到其作為最小值能延伸的最長區間：

• 向左延伸至第一個 小於 a[i] 的位置（左邊界 L）。
• 向右延伸至第一個 小於 a[i] 的位置（右邊界 R）。
• 則 a[i] 是長度為 len = R - L - 1 區間內的最小值，且是該長度所有區間最小值的候選最大值。

維護遞增棧，彈出時即可確定右邊界，棧中前一元素為左邊界。

算法流程

1. 掃描數組，維護遞增棧（存索引）。
2. 元素入棧前，彈出所有 ≥ 當前值的元素，計算其區間長度 len，更新 ans[len] = max(ans[len], val)。
3. 掃描結束後，依次彈出棧中剩餘元素，同樣更新答案。
4. 由於長度較短的區間最大最小值不小於長區間，反向掃描修正：ans[i] = max(ans[i], ans[i+1])。

關鍵代碼