原题链接：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
输入样例：
代码语言：javascript复制3 4 2
1 3
2 1输出样例：
代码语言：javascript复制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数组，在遍历的时候直接计算出来出来面积，代码很简短也优化了空间复杂度。
代码语言：javascript复制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;
}写在最后：
单调栈问题比较难理解，网上有很多版本，大家选择一个适合自己的当板子记住就行了，在学习单调栈的时候有几篇博客写的是不错的：
[数据结构]---单调栈-CSDN博客
[数据结构]——单调栈-CSDN博客
另外y总的讲解此题也是不错的选择：AcWing 1413. 矩形牛棚（每日一题）_哔哩哔哩_bilibili
学习单调栈可以去洛谷做一下入门单调栈：【模板】单调栈 - 洛谷
文章尚有不足，请各位大佬指出，若有更好的解法及模板大家一起分享。
PS:图为y总B站视频提供——作者：yxc
