首页 > 代码库 > Largest Rectangle in Histogram及二维解法
Largest Rectangle in Histogram及二维解法
昨天看岛娘直播解题,看到很经典的一题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)
Largest Rectangle in Histogram及二维解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。