Leetcode系列：84. Largest Rectangle

刷题难度：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

答案：

class Solution:
    def largestRectangleArea(self, height):
        """
        :type heights: List[int]
        :rtype: int
        """
        n = len(height)

        # left[i], right[i] represent how many bars are >= than the current bar

        left = [1] * n
        right = [1] * n
        max_rect = 0

        # calculate left
        for i in range(0, n):
            j = i - 1
            while j >= 0:
                if height[j] >= height[i]:
                    left[i] += left[j]
                    j -= left[j]
                else: break

        # calculate right
        for i in range(n - 1, -1, -1):
            j = i + 1
            while j < n:
                if height[j] >= height[i]:
                    right[i] += right[j]
                    j += right[j]
                else: break

        for i in range(0, n):
            max_rect = max(max_rect, height[i] * (left[i] + right[i] - 1))

        return max_rect

解题思路：

前两个for循环中，left[ ] 可以计算出在数组中 height[i] 的左边有多少数字大于等于 height[i] （包括它自身），同理，right[ ] 可以计算出数组中 height[i] 的右边有多少数字大于等于 height[i] （包括它自身）。
计算的结果为：

for循环的可视化结果

注：

可视化工具地址：http://www.pythontutor.com/live.html#mode=edit

在最后一层循环中，高度为height[i] 的值，宽度为left[i] + right[i] -1 ,可以求出面积。

结果：116ms, beats:41.8%