单调栈（最⼤矩形⾯积）单调栈求最⼤矩形的⼀类题：
1.简单的模板题：
直⽅图是由在公共基线处对齐的⼀系列矩形组成的多边形。
矩形具有相等的宽度，但可以具有不同的⾼度。
例如，图例左侧显⽰了由⾼度为2,1,4,5,1,3,3
通常，直⽅图⽤于表⽰离散分布，例如，⽂本中字符的频率。
现在，请你计算在公共基线处对齐的直⽅图中最⼤矩形的⾯积。
图例右图显⽰了所描绘直⽅图的最⼤对齐矩形。
输⼊格式
输⼊包含⼏个测试⽤例。
每个测试⽤例占据⼀⾏，⽤以描述⼀个直⽅图，并以整数 n 开始，表⽰组成直⽅图的矩形数⽬。然后跟随 n 个整数 h1，…，hn。
这些数字以从左到右的顺序表⽰直⽅图的各个矩形的⾼度。
每个矩形的宽度为 1。
同⾏数字⽤空格隔开。
当输⼊⽤例为 n=0 时，结束输⼊，且该⽤例不⽤考虑。
输出格式
对于每⼀个测试⽤例，输出⼀个整数，代表指定直⽅图中最⼤矩形的区域⾯积。
每个数据占⼀⾏。
请注意，此矩形必须在公共基线处对齐。
数据范围
1≤n≤100000
0≤hi≤1000000000
输⼊样例：
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
输出样例：
8
4000
这个题为什么可以⽤单调栈呢：
例如：栈中有1，4，6⽽这时来了⼀个3，你会发现有1和将要插⼊的3的时候这个4，6是⽤不着的，这是4和6就可以出栈，这不就是⼀个单调递增的栈吗
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//l[i], r[i]表⽰第i个矩形的⾼度可向两侧扩展的左右边界
int h[N], q[N], l[N], r[N];
typedef long long ll;
int main()
{
int n;
while(scanf("%d", &n), n)
{
for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);
h[0] = h[n + 1] = -1;
int tt = -1;
q[++ tt] = 0;
for(int i = 1; i <= n; i ++)
{
while(h[q[tt]] >= h[i])  tt --;
l[i] = q[tt]+1;
q[++ tt] = i;
}
tt = -1;
q[++ tt] = n + 1;
for(int i = n; i; i --)
{
while(h[q[tt]] >= h[i])  tt --;
r[i] = q[tt]-1;
q[++ tt] = i;
}
ll res = 0;
for(int i = 1; i <= n; i ++)  res = max(res,(ll)h[i]*(r[i]-l[i]+1));
printf("%lld\n", res);
}
return0;
}
这个题就是让你⼀个全是'F'的最⼤矩阵的⾯积
有⼀天，⼩猫 rainbow 和 freda 来到了湘西张家界的天门⼭⽟蟾宫，⽟蟾宫宫主蓝兔盛情地款待了它们，并赐予它们⼀⽚⼟地。
这⽚⼟地被分成N×M
现在 freda 要在这⾥卖萌。。。它要⼀块矩形⼟地，要求这⽚⼟地都标着F并且⾯积最⼤。
但是 rainbow 和 freda 的 OI ⽔平都弱爆了，不出这块⼟地，⽽蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你到的⼟地⾯积为S
输⼊格式
第⼀⾏包括两个整数N,M
接下来N
每⾏末尾没有多余空格。
输出格式
输出⼀个整数，表⽰你能得到多少银⼦，即(
数据范围
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
这个题就是维护⼀个h[i][j]和l[i][j]和r[i][j]，最后的答案就是max(h[i][j]*(r[i][j]-l[i][j]+1))这个题就是上⼀个题的进阶版，
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e3+100;
char s[maxn][maxn];
int a[maxn][maxn];
int up[maxn][maxn];
int l[maxn][maxn];
int r[maxn][maxn];
int q[maxn];
int main(){
int n,m;
cin>>n>>m;
for (int i = 1; i <= n; i ++ ){
for(int j=1;j<=m;j++){
cin>>s[i][j];
if(s[i][j]=='F'){
a[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]){
up[i][j]=up[i-1][j]+1;
}
else{
up[i][j]=0;
}
}
}
for(int i=1;i<=n;i++){
int tt=-1;
up[i][0]=up[i][m+1]=-1;
q[++tt]=0;
for(int j=1;j<=m;j++){//维护单调递增的栈
while(up[i][j]<=up[i][q[tt]]) tt--;
l[i][j]=q[tt]+1;
q[++tt]=j;
}
tt=-1;
q[++tt]=m+1;
for(int j=m;j>=1;j--){
while(up[i][q[tt]]>=up[i][j]) tt--;
r[i][j]=q[tt]-1;
q[++tt]=j;
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//cout<<i<<" "<<j<<" "<<l[i][j]<<" "<<r[i][j]<<" "<<up[i][j]<<endl;
ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
}
}
cout<<ans*3<<endl;
}
给你⼀个⼆进制矩阵 matrix ，它的⼤⼩为 m x n ，你可以将 matrix 中的列按任意顺序重新排列。请你返回最优⽅案下将 matrix 重新排列后，全是 1 的⼦矩阵⾯积。
⽰例 1：
输⼊：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图⽅式重新排列矩阵的每⼀列。
最⼤的全 1 ⼦矩阵是上图中加粗的部分，⾯积为 4 。
⽰例 2：
输⼊：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图⽅式重新排列矩阵的每⼀列。
最⼤的全 1 ⼦矩阵是上图中加粗的部分，⾯积为 3 。
⽰例 3：
输⼊：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有⽐⾯积为 2 更⼤的全 1 ⼦矩形。
⽰例 4：
输⼊：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的⼦矩阵，所以⾯积为 0 。
提⽰：
m == matrix.length
n == matrix[i].length
1 <= m * n <= 105
matrix[i][j] 要么是 0 ，要么是 1 。
这个题⽐上⼀个还简单就是维护⼀个h[i][j]，他说可以交换任意列的次序，那么你在遍历每⼀列的时候拍个序就⾏；class Solution {
public:
int largestSubmatrix(vector<vector<int>>& w) {
printf输出格式 同行int n=w.size(),m=w[0].size();
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
if(w[i][j]){
w[i][j]+=w[i-1][j];
}
}
}
int ans=0;
vector<int>q(m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
q[j]=w[i][j];
}
sort(q.begin(),q.end(),greater<int>());
for(int j=0;j<m;j++){
ans=max(ans,q[j]*(j+1));
}
}
return ans;
}
};

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。