n (≤2×10⁵) 隻熊站成一排,高度 a[i]。對每個長度 x (1≤x≤n),求所有長度為 x 的連續區間中,最小值的最大值。
對每個元素 a[i],找到它作為最小值的最大區間:左邊界 L[i] 為左側第一個 < a[i] 的位置,右邊界 R[i] 為右側第一個 < a[i] 的位置。則 a[i] 是長度 len = R[i] - L[i] - 1 區間內的最小值,且對於所有 ≤ len 的長度,a[i] 都可能是最小值的候選。
用單調遞增棧求 L[i], R[i]。維護 ans[len] = max(ans[len], a[i])。
最後從 n-1 遞減到 1:ans[i] = max(ans[i], ans[i+1])(長度更長的區間最小值的最大值,對較短長度也成立)。