首页 > 其他 > 详细

Largest Rectangle in Histogram

时间:2014-12-03 22:41:26      阅读:293      评论:0      收藏:0      [点我收藏+]

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.

bubuko.com,布布扣

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

 

bubuko.com,布布扣

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

 

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

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int ret = 0;
        height.push_back(0);
        vector<int> index;

        for(int i = 0; i < height.size(); i++)
        {
            while(index.size() > 0 && height[index.back()] >= height[i])
            {
                int h = height[index.back()];
                index.pop_back();

                int sidx = index.size() > 0 ? index.back() : -1;
                if(h * (i-sidx-1) > ret)
                    ret = h * (i-sidx-1);
            }
            index.push_back(i);
        }

        return ret;
    }
};

 

Largest Rectangle in Histogram

原文:http://www.cnblogs.com/code-swan/p/4141202.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!