[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*   博客：-----------------------------------------*/#include 
     
      #include 
      
       #include 
       
        using namespace std;class Solution {public:    int largestRectangleArea(vector
        
         & height) {        int maxArea = 0;        int size = height.size();        if(size <= 0){            return maxArea;        }//if        // 下标        stack
         
           indexStack;        int top,width;        for(int i = 0;i < size;++i){            // 栈空或上升序列 压入栈            if(indexStack.empty() || height[indexStack.top()] <= height[i]){                indexStack.push(i);            }//if            // 一旦下降了计算面积            else{                top = indexStack.top();                indexStack.pop();                // 栈为空 表示从第一个到当前的最低高度                width = indexStack.empty() ? i : (i - indexStack.top() - 1);                maxArea = max(maxArea,height[top] * width);                // 保持i的位置不变                --i;            }//else        }//for        // 计算剩余上升序列面积        while(!indexStack.empty()){            top = indexStack.top();            indexStack.pop();            width = indexStack.empty() ? size : (size - indexStack.top() - 1);            maxArea = max(maxArea,height[top] * width);        }//while        return maxArea;    }};int main(){    Solution s;    //vector
          
            height = {2,1,5,6,2,3}; //vector
           
             height = {2,1}; //vector
            
              height = {1,2,3}; //vector
             
               height = {2,1,2}; vector
              
                height = { 4,2,0,3,2,5}; cout<
               
                <

运行时间

这里写图片描述