前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 84 Largest Rectangle in Histogram

Leetcode 84 Largest Rectangle in Histogram

作者头像
triplebee
发布2018-01-12 14:57:48
4290
发布2018-01-12 14:57:48
举报

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example, Given heights = [2,1,5,6,2,3], return 10.

求最大矩形的面积,

一开始是把它当作DP求解的,即求最大子矩阵,复杂度n方,发现速度不是很快。

然后有了下面的想法,维护一个严格单调递增的数组和一个记录前缀长度的数组,扫描heights,

每次扫到的高度大于或等于数组的最后一个元素,则需要计算之前的结果,并将最后一个元素剔除,反复这个过程。

直到扫到的高度小于数组的最后一个元素,这是将此高度插入。

代码语言:javascript
复制
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()==0) return 0;
        vector<int> x(1,-2),y(1,1);
        heights.push_back(-1);
        int result=0;
        for(int i=0;i<heights.size();i++)
        {
            int temp=1;
            while(x[x.size()-1]>=heights[i]) 
            {
                result=max(result,x[x.size()-1]*(y[x.size()-1]+temp-1));
                temp+=y[x.size()-1];
                x.pop_back();
                y.pop_back();
            }
            x.push_back(heights[i]);
            y.push_back(temp);
        }
        return result;
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-09-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档