单调栈与单调队列（对数组元素下标的操作）

用空间换时间，每个元素的下标仅入栈（队列）一次，时间复杂度均为O(n)

一，数组模拟栈：

1.初始栈为空：top=-1;
2.入栈：Stack[++top]=x;
3.出栈：if(top!=-1)top--; (注意栈为空时不能出栈)
4.栈顶元素：Stack[top];

二，数组模拟双端队列：

1.初始队列为空：hh==tt=0;
2.队尾入队：Queue[++tt]=x;队尾出队：tt--;
3.队头出队：hh++;
4.队头元素 Queue[hh+1];

三，单调栈（元素下标维护单调栈）

实现查找数列中每个数的左边（右边）第一个比它大（小）的数的下标，栈顶元素即为当前要查找的数的下标

四，单调队列（元素下标维护双端队列）

实现查找窗口中的最大（小）值的下标，队头即为当前要查找的最值的下标（也叫滑动窗口）

1.AcWing131.直方图中最大的矩形

单调栈

思路：
1.用单增栈顺序遍历数组，预处理出l[i]：h[i]左边第一个比h[i]小的数的下标
2.用单增栈逆序遍历数组，预处理出r[i]：h[i]右边第一个比h[i]小的数的下标
3.O(n)遍历取最大的{h[i]*(r[i]-l[i]-1)，注意边界问题

点击查看代码

2.AcWing 135.最大子序和

单调队列+前缀和

思路：
1.容易想到暴力O(n^3)，加上前缀和O(n^2)，再加上单调队列O(n)
2.先将原数组前缀和处理
3.初始化前缀和第一个值a[0]入队（[1,n]的n个数前缀和处理后左边界有[0,n]的n+1个数）
4.枚举右端点i，单调队列记录[i-m,i-1]最小值（因为最短长度为1）
5.res对每个右端点的情况取（a[i]-a[队头]）的最大值

点击查看代码

3.AcWing 1413.矩形牛棚

枚举下边界+求直方图最大矩形（单调栈）

思路：
1.递推出每个土地的高度h[i][j]
2.枚举每一行作为直方图的下边界，求直方图的最大面积

点击查看代码

4.AcWing 4964.子矩阵

二维单调队列

思路：
1.先用单调队列横向预处理出每一行最大值rmax[r][i]和最小值rmin[r][i]
（滑动窗口长度为b）（i的范围为[b,m]）
2.再在rmax[r][i]和rmin[r][i]的基础上，用单调队列纵向处理出cmax[i],cmin[i]
（滑动窗口长度为a）（i的范围为[a,n]）
3.取所有cmax[i]*cmin[i]之和即可

点击查看代码