#84 Largest Rectangle in Histogra——Top 100 Liked Questions-蒲公英云

#84 Largest Rectangle in Histogra——Top 100 Liked Questions

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

第一次：暴力解法，时间超时：遍历每个元素，设定两个指针left和right，初始值均为i，找height[i]两边比其大的元素，遇到比其小的就停止，当左右两边都没有比height[i]大的元素时，计算面积：height[i] * （right-left+1），并更新最大面积

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights:
            return 0
        m = len(heights)
        res = 0
        for i in range(0, m):
            left, right = i, i
            while left - 1 >= 0 and heights[left - 1] >= heights[i]:
                left = left - 1
            while right + 1 <= m - 1 and heights[right + 1] >= heights[i]:
                right = right + 1
            area = heights[i] * (right - left + 1)
            res = max(area, res)
        return res

Time Limit Exceeded

第二次：采用单调栈

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights:
            return 0
        heights.append(0)
        stack = [-1]
        L = len(heights)
        ans = 0
        for i in range(L):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h * w)
            stack.append(i)
        return ans