本文主要是介绍AcWing 152. 城市游戏 单调栈，栈解法，悬线法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：https://www.acwing.com/problem/content/description/154/
题目描述
有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成N*M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着’F’并且面积最大。
但是rainbow和freda的OI水平都弱爆了，找不出这块土地，而蓝兔也想看freda卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为S，它们将给你3*S两银子。
输入格式
第一行包括两个整数N,M，表示矩形土地有N行M列。
接下来N行，每行M个用空格隔开的字符’F’或’R’，描述了矩形土地。
每行末尾没有多余空格。
输出格式
输出一个整数，表示你能得到多少银子，即(3*最大’F’矩形土地面积)的值。
数据范围
1≤N,M≤1000
样例
输入样例：
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
输出样例：
45
思路：要由F组成最大的矩阵，等价于求直方图的最大面积。
先统计第一行到每一行的连续矩形个数。如果下一行对应为'F'，那么
h[i][j]=h[i-1][j]+1;否则，h[i][j]=0;
接下来枚举每一行，求直方图最大面积。
求直方图最大面积模板：
a[n+1]=p=0;//增加一个高度为0的矩形，以免在扫描结束后还有剩余矩形
for(int i=1;i<=n;i++){if(a[i]>s[p]){//当前矩形比栈顶矩形高，直接入栈，并设置宽度为1s[++p]=a[i];w[p]=1;}else{int width=0;while(s[p]>a[i]){width+=w[p];//累计被弹出的矩形宽度之和ans=max(ans,width*s[p]);//不断更新面积最大值p--;//弹出}s[++p]=a[i],w[p]=width+1;//整个出栈过程结束后，把一个高度为当前矩形高度，宽度为累计值的新矩形入栈}
}代码如下：
（1)单调栈解法：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int h[N][N];//存储F的数量
int n,m,s[N],w[N];//s为栈，w为宽度
int get(int a[]){//对于每一行 int p=0,ans=0;a[m+1]=0; for(int i=1;i<=m+1;i++){if(a[i]>s[p]){//如果比栈顶元素高，直接进栈 s[++p]=a[i];w[p]=1;//宽度为1 }else{int width=0;while(s[p]>a[i]){width+=w[p];//累计被弹出的矩形之和 ans=max(ans,width*s[p]);//p--; }s[++p]=a[i],w[p]=width+1;//把一个高度为当前矩形高度，宽度为累计值的新矩形入栈 }}return ans;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char ch;cin>>ch;if(ch=='F') h[i][j]=h[i-1][j]+1;else h[i][j]=0;}}int ans=0;for(int i=1;i<=n;i++) ans=max(ans,get(h[i]));//枚举每一行，不断更新 cout<<ans*3<<endl;return 0;
}（2）悬线法：https://www.cnblogs.com/Tyouchie/p/11382288.html
代码如下：https://www.acwing.com/solution/content/4873/
补充：求直方图最大面积：栈解法：https://www.nowcoder.com/questionTerminal/e3f491c56b7747539b93e5704b6eca40
代码如下：
int get(vector<int> &height){int ans=0;stack<int> st;for(int i=0;i<height.size();i++){if(st.empty()||height[i]>st.top()){//大于栈顶元素，入栈 st.push(height[i]);}else{int count=0;//记录弹出次数 /*如果栈非空 同时高度小于等于栈顶元素，那么就一直弹出栈顶元素，边弹出边计算更新ans, 直至height[i]>栈顶元素，此时将弹出的那几个数用height[i]替代入栈，最后height[i]自己再入栈 */while(!st.empty()&&height[i]<=st.top()){count++;ans=max(ans,st.top()*count);st.pop();}while(count--){st.push(height[i]);//让这个代替前面弹出的几个入栈 }st.push(height[i]);//自己入栈 }}int count=1;while(!st.empty()){//最后形成一个升序的栈 ans=max(ans,st.top()*count);//不断比较并更新 st.pop();count++;}return ans;
}这篇关于AcWing 152. 城市游戏 单调栈，栈解法，悬线法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
