Largest Rectangle in Histogram

发布时间:2016-12-31 7:37:19编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"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.top()]){                s.push(i);                i++;            }else{                int cur = s.top();                s.pop();                if(s.empty()){                    res = max(res,heights[cur]*i);                }else{                    res = max(res,heights[cur]*(i-s.top()-1));                }


上一篇:识别网络应用所使用的协议Amap
下一篇:CSS3 content属性学习

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。