參考洛谷p1440求m區(qū)間內(nèi)的最小值、洛谷p1725琪露諾

1.單調(diào)隊(duì)列：p1440求m區(qū)間內(nèi)的最小值（滑動(dòng)窗口）

對(duì)于一組數(shù)據(jù)，多次求一個(gè)區(qū)間內(nèi)的最值，可以用一個(gè)雙端隊(duì)列deque維護(hù)，

struct node
{
    int val;//要比較的值
    int pos;//這個(gè)值在這組數(shù)據(jù)中的位置
}v[N];
min_que[0] = 0;
int head = 1,tail = 0;
for(int i = 1; i < n; i++){
    while((head <= tail)&&(v[tail].val >= a[i - 1]))
               tail--;//tail移動(dòng)到從尾端數(shù)第一個(gè)小于該數(shù)的位置
    v[++tail].val = a[i - 1];
    v[tail].pos = i - 1;//將該數(shù)據(jù)放到隊(duì)列中
    while((head <= tail)&&(v[head].pos < i - m))
                head++;//將不在這個(gè)區(qū)間內(nèi)的頭部去掉，
    //中間的暫時(shí)不用去掉，因?yàn)橹粫?huì)用到頭部
    min_que[i] = v[head].val;
}

2.單調(diào)隊(duì)列優(yōu)化dp：

有一種dp要尋找從 i 到 j 中最大的 dp[k] ,此時(shí)可以利用單調(diào)隊(duì)列來優(yōu)化