Skip to content

84. Largest Rectangle in Histogram

难度:Hard

刷题内容

原题连接

  • https://leetcode.com/problems/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.

Example:

Input: [2,1,5,6,2,3]
Output: 10

思路1 **- 时间复杂度: O(n^2)*- 空间复杂度: O(n)***

这题第一种思路就是用暴力的方法去解。时间复杂度为O(n^2)。遍历数组,对数组中每个元素分别向右向左找到最远,计算最大值得到结果

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        long long ans = 0;
        for(int i = 0;i < heights.size();++i)
        {
            int j = i + 1;
            long long l,r;
            for(;j < heights.size();++j)
                if(heights[j] < heights[i])
                {
                    r = (long long)heights[i] * (j - i);
                    break;
                }
            if(j == heights.size())
                r = (long long)heights[i] * (heights.size() - i);
            for(j = i - 1;j >= 0;--j)
                if(heights[j] < heights[i])
                {
                    l = (long long)heights[i] * (i - j - 1);
                    break;
                }
            if(j < 0)
                l = (long long)heights[i] * i;
            ans = max(ans,l + r);
        }
        return ans;
    }
};

思路2 **- 时间复杂度: O(n)*- 空间复杂度: O(n)***

上面第一种方法的实现中有重复计算的过程,我们用栈去解决这个问题就很好的剔除了重复计算的过程,时间复杂度降到了O(n)。先定义一个栈,我们要保证栈中的数是递增的,遍历数组,若这个数小于栈顶的数,则将栈顶的数弹出,并计算栈顶元素的最大距离,直到栈为空或者比这个数小

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        long long ans = 0;
        heights.push_back(0);
        vector<pair<long long,int> > v;
        for(int i = 0;i < heights.size();++i)
        {
            if(!v.size() || heights[i] > v[v.size() - 1].first)
                    v.push_back(make_pair(heights[i],i));
            else
            {
                int j = v.size() - 1;
                while(j > 0 && v[j].first > heights[i])
                {
                    ans = max(ans,v[j].first * (i - v[j - 1].second - 1));
                    v.pop_back();
                    --j;
                }
                if(!j && v[j].first > heights[i])
                {
                    ans = max(ans,v[j].first * (i));
                    v.pop_back();
                }
                v.push_back(make_pair(heights[i],i));
            }
        }
        return ans;
    }
};


回到顶部