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

﹏ヽ暗。殇╰゛Y 2022-01-23 01:47 136阅读 0赞

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.

![histogram.png][]  
Above is a histogram where width of each bar is 1, given height =`[2,1,5,6,2,3]`.

![histogram_area.png][]  
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
> 
>  
> 
> Runtime: 84 ms, faster than 70.78% of Python online submissions forLargest Rectangle in Histogram.
> 
> Memory Usage: 13.5 MB, less than 73.96% of Python online submissions for Largest Rectangle in Histogram.

[histogram.png]: https://assets.leetcode.com/uploads/2018/10/12/histogram.png
[histogram_area.png]: https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png