引入单调队列单调堆栈单调队列问题
rmq(x，y )是问题排列[x，y]区间内部最小值，例如： rmq (0，3 )=1
01234567314529812固定尾部查询区间最小值：rmq(x，7 )最少可记录一些因素，满足rmq (x，7 )的要求
0123456712812此时构成了单调的队列
维护固定结尾的区间最值问题
入队操作：
在进入团队之前，将先前破坏的单调性元素从团队末尾移动(保持单调性) ) ) ) ) ) ) ) ) )。
出队操作：
团队开头的要素超出区间范围时，将要素从对方中推出团队
滑动窗口(#271 ) link
原理：分别维护增减单调队列
存储a[N]数组、q[] head=tail=0单调队列下标，a[q[head]]为极值
首先对k-1个元素进行排队，首先判断是否单调，tail-head a[q[tail - 1]]=a[i]； q[tail ]=i；
滑动到k要素时开始出现极值，仍然保持单调性后进入队伍，判断队伍长度大于k时踢出队伍前列
# includeiostreamusingnamespacestd； #define MAX_N 300000int a[MAX_N 5]； int q[MAX_N 5]，head=0，tail=0； //队列存储数组下标int main () { int n，k； cin n k； for(intI=1； i=n； I ) cin a[i]； for(intI=1； i k； I ) ) while (tail-heada [ q [ tail-1 ]=a [ I ] ) tail--； //意图在团队末尾加入一个要素，首先判断是否符合单调性，不符合的要素为q[tail ]=i； //进入团队}for(intI=k； i=n； I ) ) while (tail-heada [ q [ tail-1 ]=a [ I ] ) tail--； q[tail ]=i； if(q[head]=I-k ) head； //判断队长i==k || cout '； cout a[q[head]]； } cout endl； head=tail=0； for(intI=1； i k； I ) ) while (tail-heada [ q [ tail-1 ]=a [ I ] ) tail--； q[tail ]=i； }for(intI=k； i=n； I ) ) while (tail-heada [ q [ tail-1 ]=a [ I ] ) tail--； if(q[head]=I-k ) head； q[tail ]=i； i==k || cout '； cout a[q[head]]； } cout endl； 返回0； }优化：
for(intI=1； i=n； I ) ) while (tail-heada [ q [ tail-1 ]=a [ I ] ) tail--； q[tail ]=i； if(Ik )连续； if(q[head]=I-k ) head； i==k || cout '； cout a[q[head]]； }最大子序列和(#270 ) link
前缀和差分
s0s1=s0a1s2=s1a2s3=S2 a3…sn=sn-1 ana 0a1a2a 3…anx0x1=a1-a0x2=a2-a1x3=a3-a2…xn=an-an-1原理：在前缀和序列运算中区间
保持单调递增的前缀和顺序，保持窗口大小
固定最后，向前寻找序列的最小值，减法是序列和最大值
a[]=1 -3 5 1 -2 3； s[]=1 -2 3 4 2 5
# includeiostreamusingnamespacestd； #define MAX_N
300000int s[MAX_N + 5];int q[MAX_N + 5], head, tail;int main() { int n, m, ans; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1]; ans = s[1]; for (int i = 1; i <= n; i++) { if (q[head] < i - m) head++; ans = max(ans, s[i] - s[q[head]]); while (tail - head && s[q[tail -1]] > s[i]) tail--; q[tail++] = i; } cout << ans; return 0;}关于判断队长时是否取等号
滑动窗口要取，因为下一次循环必有元素进入；
最长子序列不用，下次未必有元素进入队列，窗口长度可以小于m
总结单调队列就两步：
维护队列单调性，新元素进入队列（入队前踢出当前所有违反单调性元素）维护窗口长度，超过则弹出队首元素（队首元素，区间最值） 单调栈问题引入
给一个序列，求序列中，每个元素左侧，第一个小于它的元素
01234567314529812相较于单调队列，单调栈没有维护窗口长度操作，单调队列没窗口的话自动取前方最值
维护最近大于/小于问题
从左侧先入栈，就是维护左侧最近关系；从右侧先入栈，就是维护右侧最近关系。
最大矩形面积（#264）link
原理：选定基准板，往两边查找第一个小于基准元素，相减即为矩形边长
就是一半的单调队列问题，组成单调栈后，获取最近的小于本元素值位置
编程技巧：加入哨兵元素，保证扁矩形也符合规则
#include<iostream>using namespace std;#define MAX_N 100000long long a[MAX_N + 5];long long s[MAX_N + 5], top = -1;long long l[MAX_N + 5], r[MAX_N + 5];int main() { long long n; cin >> n; for (long long i = 1; i <= n; i++) cin >> a[i]; a[0] = a[n + 1] = -1; s[top = 0] = 0;//清空栈 for (long long i = 1; i <= n; i++) { while(a[s[top]] >= a[i]) top--; l[i] = s[top]; s[++top] = i; } s[top = 0] = n + 1; for (long long i = n; i >= 1; i--) { while (a[s[top]] >= a[i]) top--; r[i] = s[top]; s[++top] = i; } long long ans = 0; for (long long i = 1; i <= n; i++) { ans = max(ans, a[i] * (r[i] - l[i] - 1)); } cout << ans << endl; return 0;} 双生序列（#372）link
#include<iostream>using namespace std;#define MAX_N 500000int a[MAX_N + 5];int b[MAX_N + 5];int sa[MAX_N + 5], sa_top = -1;int sb[MAX_N + 5], sb_top = -1;int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; sa[sa_top = 0] = 0, sb[sb_top = 0] = 0; int num = 1; for (int i = 1; i <= n; i++){ while (a[sa[sa_top]] > a[i]) sa_top--; sa[++sa_top] = i; while (b[sb[sb_top]] > b[i]) sb_top--; sb[++sb_top] = i; if (sa_top != sb_top) { num = i - 1; break; } } cout << num << endl; return 0;}优化：
#include<iostream>using namespace std;#define MAX_N 500000int a[MAX_N + 5], b[MAX_N + 5];//检查过程会踢出元素，可以利用检查过的空间存储单调栈元素int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; int p = 1, topa = -1, topb = -1; while (p < n) { while (topa != -1 && a[p] <= a[topa]) topa--; while (topb != -1 && b[p] <= b[topb]) topb--; if (topa - topb) break; a[++topa] = a[p]; b[++topb] = b[p]; p++; } cout << p << endl; return 0;}压栈和进队列不同点
栈top指针指向栈顶元素；队列tail指针指向队尾元素+1