是說我也不知道我這個解的複雜度 但還是AC了XD

int ary[1e6],ans[1e6]; // ary 題目給的數列   ans 最靠近自己且比自己矮的人的編號(也就是題目要我們輸出的答案

從1~n建ans

ans[1]必為0

假設我們建到了x 

就用之前1~x-1建好的ans來找出這個ans[x]

以下會有三種狀況

ary[x]>ary[x-1] 那麼 ans[x] = x-1

ary[x]==ary[x-1] ans[x] = ans[x-1]

ary[x]<ary[x-1] 那就可以基於ans[x-1] 可以知道 x-1~ans[x-1] 之間的數 都比ary[x]大 所以可以直接跳過 然後就繼續判斷ans[x-1]~ans[ans[x-1]] 就好囉~

寫起來的話會有兩層for迴圈

第一層是1~n

 第二層是x~0

歐對了 如果數列是嚴格遞增 最壞會到n^2

如果被刻意卡的話就不行了 qwq

這題是單調堆疊(monotonic stack)的裸題