# 中電會六月主題課程--進階動態規劃 --- 點名 回饋表單 --- ## 單調棧(Monotonic stack) ----  ---- [Nearest Smaller Values](https://cses.fi/problemset/task/1645) ---- ### 觀察  有一些數字不會是答案 例如位置1的5，因為他右邊有一個1。當右邊某個數字(假設$x$)往左邊掃時，他一定會先掃到1才掃到5，此時5永遠不可能是答案，因為若5比$x$小，則1也會比$x$小。 ----  ---- $$ \begin{aligned} &\text{for all } (i,j) \text{ where }i<j<n \text{ ,} \\ &\text{if } a_i\geq a_j \text{ ,}\\ &i \text{ is not the answer for any } k>j \end{aligned} $$ ---- 把不可能的都刪掉後，最後剩下的一定是**嚴格遞增**的 ---- ### 實作  ---- ```cpp= stack<int> st; st.push(0); vector<int> v(n+1); v[0]=-1; for(int i=0;i<n;i++){ int a; cin>>a; v[i+1]=a; } for(int i=1;i<n+1;i++){ while(v[st.top()]>=v[i]) st.pop(); cout<<st.top()<<" "; st.push(i); } ``` ---- ### 延伸 [Advertisement](https://cses.fi/problemset/task/1142) [Maximum Building I](https://cses.fi/problemset/task/1147) --- ## 單調佇列(Monotonic queue) 我都叫他單調隊列 ---- 實作上會使用deque  就只是變兩頭都可以操作而已 ---- [a146. Sliding Window](https://zerojudge.tw/ShowProblem?problemid=a146) ---- ### 直覺解法 維護一個multiset，每次輸出最大/小的，再刪掉過期的並加入新的 $\text{O}(n\log n)$ ---- ### 觀察  ---- ### 延伸 [Maximum Subarray Sum II](https://cses.fi/problemset/task/1644/) 有限個數的多重背包問題 --- ## [斜率優化](https://hackmd.io/@tmting39/ByGhMYmra)