单调栈 与 单调队列

单调栈

使用栈维护一个固定的边长窗口[1,i]内的单调序列，从栈顶取最值，进行计算或转移。

tt = -1 ;
_rep(i,1,n){
    cin >> a[i] ;
    while(tt != -1 && a[h[tt]] < a[i]){
        b[h[tt]] = i ;
        tt -- ; 
    }
    h[++tt] = i ;
}

求解最长上升 / 下降子序列就用到了这个优化。

---

单调队列

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

以最小值为例

1. 队尾出队的条件：队列不为空且新元素更优，队中旧元素队尾出队
2. 每个元素必然从队尾进队一次
3. 队头出队的条件：队头元素滑出了窗口

注意：队列中存储元素的下标，方便判断队头出队。

hh =0 , tt = -1 ;//清空队列
_rep(i,1,n){
    cin >> a[i] ;
    while(hh <= tt && a[h[tt]] >= a[i]){//新的元素比队尾更优
        tt -- ;
    }
    h[++tt] = i ;//队尾入队新元素，如果并没有比新的元素更优也不会破坏队头的最小值
    if(h[hh] < i - k + 1) hh ++ ;//对头出队
    if(i >=k){
        cout << a[h[hh]] << " " ;
    } 
}

求解多重背包问题的优化