昨天看岛娘直播解题,看到很经典的一题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)

最新文章

  1. Flex 布局相关用法
  2. Nightmare
  3. EL函数
  4. BCEC手动验证业务方法
  5. tomcat7.0的源码下载
  6. 【Demo 0003】Android 事件
  7. 关于cin.getline和cin.get
  8. PJSUA2开发文档--第九章 PJSUA2应用程序示例
  9. Python_Mix*re模块,元字符,量词
  10. 《CLR Via C#》读书笔记:27.计算限制的异步操作
  11. 2018-03-11 20165235 祁瑛 Java第二周考试总结
  12. JavaScript基础知识(初识JS)
  13. linux command line send email
  14. Codeforces Round #519
  15. git命令行的操作实例教程
  16. unigui作中间件使用
  17. 使用浏览器,调试js代码
  18. 蓝牙协议 HFP,HSP,A2DP,A2DP_CT,A2DP_TG,AVRCP,OPP,PBAP,SPP,FTP,TP,DTMF,DUN,SDP
  19. 纯 html 以及 js 多域名跳转
  20. [Javascript] Closure Cove, Common mistake

热门文章

  1. zabbix 报警发送企业威信
  2. 带你理解MST性质
  3. [python]Appium+python +pytest 实现APP自动化,基于安卓
  4. flask cache
  5. Merge into用法总结
  6. asp.net.core教程
  7. 记一次 IIS 站点配置文件备份和还原,物理路径文件批量备份
  8. c语言1左移32位(1&lt;&lt;32)是多少,左移-1位呢
  9. Java安全之基于Tomcat的Filter型内存马
  10. [hdu4388]Stone Game II