首页 > itarticle > largest rectangle in histogram

largest rectangle in histogram

admin 11月 13, 2020 0

Description

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.

class  {
public:
    int largestRectangleArea(vector<int>& heights) {
        
    }
};

what I think

正常的思路就是遍历每一个数，对每一个数看前面和后面有没有比她小的，有则count++，没有跳出循环，利用count*height来算出结果。代码就略了。但是N^2的时间Leetcode根本不接受啊!没办法上网找一下灵感~

Advanced

堆栈 http://blog.csdn.net/yutianzuijin/article/details/52072427

class  {
public:
    int largestRectangleArea(vector<int> &height) {
        int ret = 0;
        stack<int> stk;
        for(int i = 0; i < height.size(); i ++)
        {
            if(stk.empty() || stk.top() <= height[i])
                stk.push(height[i]);
            else
            {
                int count = 0;
                while(!stk.empty() && stk.top() > height[i])
                {
                    count ++;
                    ret = max(ret, stk.top()*count);
                    stk.pop();
                }
                while(count --)
                    stk.push(height[i]);
                stk.push(height[i]);
            }
        }
        int count = 1;
        while(!stk.empty())
        {
            ret = max(ret, stk.top()*count);
            stk.pop();
            count ++;
        }
        return ret;
    }
};