[LeetCode]*84.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 height = [2,1,5,6,2,3], return 10.

思路

我们通过一个栈记录上升的柱子，如果如果下降的柱子，可以开始计算栈顶和之前柱子构建的矩形的面积。栈保存的是柱子的下标，而不是柱子的高度，目的是方便计算矩形的面积。遇到上升的柱子，就把柱子对应的下标压入栈。

代码

/*—————————————* 日期：2015-05-13* 作者：SJF0115* 题目: 84.Largest Rectangle in Histogram* 网址：https://leetcode.com/problems/largest-rectangle-in-histogram/* 结果：AC* 来源：LeetCode* 博客：—————————————–*/;class Solution {public:int largestRectangleArea(vector<int>& height) {int maxArea = 0;int size = height.size();if(size <= 0){return maxArea;}<int> indexStack;int top,width;for(int i = 0;i < size;++i){// 栈空或上升序列 压入栈if(indexStack.empty() || height[indexStack.top()] <= height[i]){indexStack.push(i);}{top = indexStack.top();indexStack.pop();// 栈为空 表示从第一个到当前的最低高度width = indexStack.empty() ? i : (i – indexStack.top() – 1);maxArea = max(maxArea,height[top] * width);// 保持i的位置不变–i;}//else}(!indexStack.empty()){top = indexStack.top();indexStack.pop();width = indexStack.empty() ? size : (size – indexStack.top() – 1);maxArea = max(maxArea,height[top] * width);}//whilereturn maxArea;}};int main(){Solution s;<int> height = {4,2,0,3,2,5};cout<<s.largestRectangleArea(height)<<endl;return 0;}

运行时间

，当你能飞的时候就不要放弃飞