HDU -1506 Largest Rectangle in a Histogram&&51nod 1158 全是1的最大子矩阵 (单调栈)

叁歲伎倆 2023-10-11 09:33 16阅读 0赞

单调栈和队列讲解：[传送门][Link 1]

HDU -1506题意：

就是给你一些矩形的高度，让你统计由这些矩形构成的那个矩形面积最大

![1633695-20190731172112278-778926674.png][]

如上图所示，如果题目给出的全部是递增的，那么就可以用贪心来解决

从左向右依次让每一个矩形的高度当作最后的高度，来从中选取最大值就可以了

但是如果它不是递增的，中间会出现低谷，那么要还想运用贪心策略就要把之前高度大于它的全部扔掉，但是再扔掉他们之前还要判断一下以他们为最后答案的高度可不可行，这样我们就是在构造一个递增序列，可以用栈来维护它

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<queue>
     5 #include<algorithm>
     6 #include<vector>
     7 #include<stack>
     8 using namespace std;
     9 const int maxn=100080;
    10 int n,height[maxn],width[maxn],Stack[maxn],top=0;
    11 long long work()
    12 {
    13     long long ans=0;
    14     for(int i=1;i<=n+1;++i)
    15     {
    16         if(height[i]>Stack[top])
    17         {
    18             Stack[++top]=height[i];
    19             width[top]=1;
    20         }
    21         else
    22         {
    23             int widthsum=0;
    24             while(Stack[top]>height[i])
    25             {
    26                 widthsum+=width[top];
    27                 ans=max(ans,(long long)widthsum*Stack[top]);
    28                 top--;
    29             }
    30             Stack[++top]=height[i];
    31             width[top]=widthsum+1;
    32         }
    33     }
    34     return ans;
    35 }
    36 int main()
    37 {
    38     while(~scanf("%d",&n))
    39     {
    40         if(!n) break;
    41         for(int i=1;i<=n;++i)
    42             scanf("%d",&height[i]);
    43         height[n+1]=0;
    44         long long ans=work();
    45         printf("%lld\n",ans);
    46     }
    47     return 0;
    48 }

传送门：[51nod 1158][]

51nod 1158题意：

就是给你输入一个n行m列的矩形，里面由1或0构成，你要从中找出来最大的被1填充的矩形

题解：

这一道题感觉和上一个道题很相似，唯一不同的是，上一道题告诉你了高度，但是这一道题要求你自己找出来

思路：第一步还是降维操作，用a\[i\]\[j\]记录以第i行为底的全1直方图的高，如对于矩阵：

1 1 1 0

0 0 1 1

1 1 0 1

1 1 1 0

对于上面这个我们可以把它转化成

1 1 1 0

0 0 2 1

1 1 0 2

2 2 1 0

这样处理后就和上一道题差不多了，因为每一行就相当于上一道题输入的那一行数据，我们只需要对这几行一一用单调栈处理就可以了

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 
     3 using namespace std;
     4 
     5 const int N = 1e5 + 7;
     6 
     7 int n, m, x, ans;
     8 
     9 int h[N], a[N];
    10 
    11 stack <int> s;
    12 
    13 int main()
    14 
    15 {
    16 
    17     scanf("%d%d",&m,&n);
    18 
    19     for(int i = 0; i < m; i++)
    20 
    21     {
    22 
    23         for(int j = 1; j <= n; j++)
    24 
    25         {
    26 
    27             scanf("%d", &x);
    28 
    29             if(x == 1) a[j] += 1;
    30 
    31             else a[j] = 0;
    32 
    33             h[j] = a[j];
    34 
    35         }
    36 
    37         s.push(0);
    38 
    39         for(int j = 1; j <= n + 1; j++)
    40 
    41         {
    42 
    43             while(h[j] < h[s.top()])
    44 
    45             {
    46 
    47                 int index = s.top();
    48 
    49                 s.pop();
    50 
    51                 int tmp = (j - 1 - s.top()) * h[index];//因为我们维护的是一个递增
    52                 //序列，所以目前正在枚举这个位置，跟栈顶中位置之间的全部位置的高度
    53                 //都是大于这个正在枚举的位置的高度
    54                 ans = max(ans, tmp);
    55 
    56             }
    57 
    58             s.push(j);
    59 
    60         }
    61 
    62     }
    63 
    64     cout << ans << endl;
    65 
    66 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11277980.html

[Link 1]: https://blog.csdn.net/Prasnip_/article/details/83690038
[1633695-20190731172112278-778926674.png]: https://img2018.cnblogs.com/blog/1633695/201907/1633695-20190731172112278-778926674.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[51nod 1158]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1158