[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 <iostream>
#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        int maxArea = 0;
        int size = height.size();
        if(size <= 0){
            return maxArea;
        }//if
        // 下标
        stack<int> 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<int> height = {2,1,5,6,2,3};
    //vector<int> height = {2,1};
    //vector<int> height = {1,2,3};
    //vector<int> height = {2,1,2};
    vector<int> height = {4,2,0,3,2,5};
    cout<<s.largestRectangleArea(height)<<endl;
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>