Largest Rectangle in Histogram及二维解法
2024-09-06 18:46:47
昨天看岛娘直播解题,看到很经典的一题Largest Rectangle in Histogram
题目地址:https://leetcode.com/problems/largest-rectangle-in-histogram/#/description
解法:
int largestRectangleArea(vector<int> &h) {
stack<int> S;
h.push_back(0);
int sum = 0;
for (int i = 0; i < h.size(); i++) {
if (S.empty() || h[i] > h[S.top()]) S.push(i);
else {
int tmp = S.top();
S.pop();
sum = max(sum, h[tmp]*(S.empty()? i : i-S.top()-1));
i--;
}
}
return sum;
}
从左向右扫描矩形柱,当右边高于左边时入栈,否则计算栈顶矩形块向右边衍伸的最大面积.
由于入栈策略的制定导致了栈内上方的矩形块高度始终高于下方矩形块的高度,所以扫描最大面积时直接拿当前栈顶的矩形块高度乘以其到当前矮矩形块的距离-1即可(因为其右边到当前矮矩形块左边之间的所有矩形块高度一定高于该矩形块)
做法十分巧妙,时间复杂度只有O(n)
他的变种就是http://poj.org/problem?id=3494
矩形块被01数组取代
解法:
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; int n,m,h[100005],top,ans; struct Node {
int h,sta;//sta表示高度h的起始下标
}s[100005]; int main() {
int hh,t;
while(scanf("%d%d",&n,&m)==2) {
memset(h,0,sizeof(h));
ans=0;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
scanf("%d",&hh);
h[j]=hh==0?0:h[j]+1;
} t=m;
h[++t]=-1;//令最后一个元素的下一个高度为-1,避免循环完毕后还要弹出栈中所有元素
s[0].h=-1;
s[0].sta=top=0;
for(int k=1;k<=t;++k) {
if(h[k]>=s[top].h) {
s[++top].h=h[k];
s[top].sta=k;//其起始下标就是自己的下标
}
else {
while(h[k]<s[top].h) {
ans=max(ans,(k-s[top].sta)*s[top].h);
--top;//弹出栈顶元素
}
s[++top].h=h[k];//其起始下标是弹出的最后一个元素的起始下标
}
}
}
printf("%d\n",ans);
}
return 0;
}
只要从底向上以每一行为base线,利用之前题目的算法逐行扫描出maxans即可
时间复杂度乘以n变成O(n2)
最新文章
- Flex 布局相关用法
- Nightmare
- EL函数
- BCEC手动验证业务方法
- tomcat7.0的源码下载
- 【Demo 0003】Android 事件
- 关于cin.getline和cin.get
- PJSUA2开发文档--第九章 PJSUA2应用程序示例
- Python_Mix*re模块,元字符,量词
- 《CLR Via C#》读书笔记:27.计算限制的异步操作
- 2018-03-11 20165235 祁瑛 Java第二周考试总结
- JavaScript基础知识(初识JS)
- linux command line send email
- Codeforces Round #519
- git命令行的操作实例教程
- unigui作中间件使用
- 使用浏览器,调试js代码
- 蓝牙协议 HFP,HSP,A2DP,A2DP_CT,A2DP_TG,AVRCP,OPP,PBAP,SPP,FTP,TP,DTMF,DUN,SDP
- 纯 html 以及 js 多域名跳转
- [Javascript] Closure Cove, Common mistake