单调栈：
单调栈是一种数据结构，通常用于解决一些与序列相关的问题，特别是在需要找到元素在序列中的「下一个更大元素」或「下一个更小元素」的情况下。单调栈可以用于在线性时间复杂度内解决这些问题。
单调栈分为单调递增栈和单调递减栈两种类型：
1.单调递增栈：
栈中元素从栈底到栈顶递增。在处理序列时，当遇到一个元素时，如果该元素比栈顶元素大，就可以将栈顶元素出栈，直到栈为空或者栈顶元素大于等于当前元素。这样，栈中的元素就是在当前元素之前且比当前元素小的元素。
2.单调递减栈：
栈中元素从栈底到栈顶递减。在处理序列时，当遇到一个元素时，如果该元素比栈顶元素小，就可以将栈顶元素出栈，直到栈为空或者栈顶元素小于等于当前元素。这样，栈中的元素就是在当前元素之前且比当前元素大的元素。
使用单调栈的一般步骤如下：
1.创建一个空栈。
2.遍历待处理的序列，对于每个元素执行以下操作：
1.如果当前元素比栈顶元素大（或小，取决于是递增栈还是递减栈），则持续将栈顶元素出栈，直到栈为空或者栈顶元素满足某种条件（例如比当前元素大或小）。
2.记录弹出的元素，说明他是单调递减栈或单调递增栈第一个不满足的元素，可以在此元素根据题意进行操作
3.如果栈不为空，比较当前元素与栈顶元素的大小：
4..将当前元素入栈。
单调栈常用于解决一些数组或序列相关的问题，如找到下一个更大元素、下一个更小元素。
模板奉上：
第一种使用stack
stack<int> st; // 单调栈，存储元素的下标 nums[n]=-1; //多加一个-1元素，防止到最后栈中还是单调递增栈，未能更新最大值 //单调递减栈就是nums[n]=0x3f3f3f; for (int i = 0; i < n; i++) { while (!st.empty() && nums[i] <= nums[st.top()]) {//不满足单调递增栈，就开始更新 res[st.top()] = i; // 弹出元素直到满足单调递增 st.pop(); } st.push(i);//下标入队 }
第二种手写一个单调栈
int work3(int h[]) { // stk 从下标 1 开始存储 int top = 0, res = 0; // 遍历到 m + 1 的位置 // 因为是在出栈时统计，为保证遍历结束时所有下标都会被统计，默认 m + 1 位置存储 0 for (int i = 1; i <= m + 1; ++ i ) { while (top && h[stk[top]] >= h[i]) { int l = stk[top -- ]; //此处添加代码根据题意进行操作 } stk[ ++ top] = i; } return res; }
原题链接：1413. 矩形牛棚 - AcWing题库
作为一个资本家，农夫约翰希望通过购买更多的奶牛来扩大他的牛奶业务。
因此，他需要找地方建立一个新的牛棚。
约翰购买了一大块土地，这个土地可以看作是一个 R 行（编号 1∼R）C 列（编号 1∼C）的方格矩阵。
不幸的是，他发现其中的部分方格区域已经被破坏了，因此他无法在整个R×C 的土地上建立牛棚。
经调查，他发现共有 P 个方格内的土地遭到了破坏。
建立的牛棚必须是矩形的，并且内部不能包含被破坏的土地。
请你帮约翰计算，他能建造的最大的牛棚的面积是多少。
输入格式
第一行包含三个整数 R,C,P。
接下来 P 行，每行包含两个整数 r,c，表示第 r 行第 c 列的方格区域内土地是被破坏的。
输出格式
输出牛棚的最大可能面积。
数据范围
1≤R,C≤3000
0≤P≤30000
1≤r≤R
1≤c≤C
输入样例：
3 4 2 1 3 2 1
输出样例：
6
解题思路：
此题主要是应用单调栈算法，不回单调栈的先去学习单调栈，单调栈主要解决的就是寻找此位置右边/左边第一个比它大/小的数，这个题为什么能够用单调栈来实现，在一个n*m的矩阵中，有一些被破坏的地，建一个牛棚无非就是抛开被破坏的地（不能占用）寻找一个最大的矩形。我们可以确定一下他的下边界，只要下边界确定了，我们利用前缀和的思想递归求一下此位置向上延申地最大长度，这样的话，我们遍历一遍下边界，每一次遍历调用一下单调栈求解此时的最大面积，最后取一个最大的即可。
单调栈：
#include<iostream> #include<stack> using namespace std; const int N=3005; int n,m,p; int h[N][N],vis[N][N]; int stk[N], top; int l[N], r[N]; int maxx; int work(int h[]) { h[0] = h[m + 1] = -1;//为了防止遍历的最后跳不出来，多加一个-1保证栈中元素可以出栈 top = 0;//初始0 stk[ ++ top] = 0; for (int i = 1; i <= m; i ++ )//寻找左边界 { while (h[stk[top]] >= h[i]) top -- ;//从栈中找左边第一个比它小的 l[i] = stk[top];//记录下来 stk[ ++ top] = i;//最后别忘了入栈 } top = 0; stk[ ++ top] = m + 1; for (int i = m; i; i -- )//寻找右边界 { while (h[stk[top]] >= h[i]) top -- ;//从栈中找右边第一个比它小的 r[i] = stk[top]; stk[ ++ top] = i; } int res = 0; for (int i = 1; i <= m; i ++ )//最后做一下面积计算即可 res = max(res, h[i] * (r[i] - l[i] - 1));//要减一不然多算一个 return res; } int main(){ cin>>n>>m>>p; for(int i=0;i<p;i++){ int x,y; cin>>x>>y; vis[x][y]=1; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(!vis[i][j]){//没有被损坏 h[i][j]=h[i-1][j]+1; } } } for(int i=1;i<=n;i++){//遍历下边界 maxx=max(maxx,work1(h[i])); } cout<<maxx<<endl; return 0; }
优化版本：
单调栈还有一种优化版本，省略了LR数组，在遍历的时候直接计算出来出来面积，代码很简短也优化了空间复杂度。
int work1(int h[]) { int top = 0, res = 0; // 因为是在出栈时统计，为保证遍历结束时所有下标都会被统计，默认 m + 1 位置存储 0 for (int i = 1; i <= m + 1; ++ i ) { while (top&& h[stk[top]] >= h[i]) { int l = stk[top-- ]; int r=(top == 0 ? i - 1 : i - stk[top] - 1); res = max(res, h[l] * r); } stk[++top] = i; } return res; }
写在最后：
单调栈问题比较难理解，网上有很多版本，大家选择一个适合自己的当板子记住就行了，在学习单调栈的时候有几篇博客写的是不错的：
另外y总的讲解此题也是不错的选择：AcWing 1413. 矩形牛棚（每日一题）_哔哩哔哩_bilibili
学习单调栈可以去洛谷做一下入门单调栈：【模板】单调栈 - 洛谷
文章尚有不足，请各位大佬指出，若有更好的解法及模板大家一起分享。 执笔至此，感触彼多，全文将至，落笔为终，感谢各位的支持。
PS:图为y总B站视频提供——作者：yxc
