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

题目大意： 给定 n 个代表在宽度为 1 的矩形条高度的非负整数, 找到它们组成的最大举行的面积。

解题思路

• 朴素的方法：只需要依次求出以第 i 个矩形条的高度为高，且包含该矩形条的最大矩形的面积 S 。然后取得最大面积，即是所求。分别向左/向右找到所有相邻且高度小于等于当前矩形条的矩形条, 他们组成的以当前矩形条的高度为高的矩形的面积即是 S, 代码描述如下：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        for(int i = 0; i < heights.size(); ++i)
        {
            int left = i, right = i;
            // 向左找到所有相邻且高度小于等于当前矩形条的矩形条
            while(left-1 >= 0 && heights[left-1] >= heights[i]) --left;
            // 向右边找到所有相邻且高度小于等于当前矩形条的矩形条
            while(right+1 < heights.size() && heights[right+1] >= heights[i]) ++right;

            ans = max(ans, heights[i]*(right-left+1));
        }

        return ans;
    }
};

• 优化： 朴素的方法复杂度为 O(n^2), 会超时(Time Limit Exceeded)。而当我们向左找所有相邻且高度小于等于当前矩形条的矩形条时，实际上可以不用重复计算 left, 而利用之前左边已经求出的结果。

AC 代码

class Solution 
{
public:
    int largestRectangleArea(vector<int>& heights)
    {
        // [startPos[i], endPos[i]]: 表示小于等于 heights[i] 的元素的包含 i 的最大区间
        vector<int> startPos(heights.size(), 0), endPos(heights.size(), heights.size());

        // 求 startPos
        for(size_t i = 1; i < heights.size(); ++i)
        {
            int left = i-1;
            startPos[i] = i;
            while(left >= 0 && heights[i] <= heights[left])
            {
                startPos[i] = startPos[left];
                left = startPos[left] - 1;
            }
        }

        // 求 endPos
        for(int i = heights.size()-1; i >= 0; --i)
        {
            int right = i + 1;
            endPos[i] = i;
            while(right < heights.size() && heights[i] <= heights[right])
            {
                endPos[i] = endPos[right];
                right = endPos[right] + 1;
            }
        }

        int ans = 0;
        for(size_t i = 0; i < heights.size(); ++i)
        {
            ans = max(ans, heights[i]*(endPos[i] - startPos[i] + 1));
        }

        return ans;
    }
};