Largest Rectangle in Histogram

发布时间:2017-2-21 10:54:11 编辑 分享查询网我要评论
本篇文章主要介绍了"Largest Rectangle in Histogram ",主要涉及到Largest Rectangle in Histogram 方面的内容,对于Largest Rectangle in Histogram 感兴趣的同学可以参考一下。

Largest Rectangle in Histogram

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.

class Solution {public:    int largestRectangleArea(vector<int>& heights) {        heights.push_back(0);        stack<int> s;        int res = 0;        int i = 0;        while(i < heights.size()){            if(s.empty() || heights[i] > heights[]){                s.push(i);                i++;            }else{                int cur =;                s.pop();                if(s.empty()){                    res = max(res,heights[cur]*i);                }else{                    res = max(res,heights[cur]*(;                }

下一篇:CSS3 content属性学习