Description:

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

Solution: Inspired by https://www.cnblogs.com/boring09/p/4231906.html 方法2

note1: 方法1好像不太对，做出来结果都不对，也没看懂如何O(n)的

note2: 思路

一开始的想法是DP，但是发现需要O(n²)，即构建一个n行n列的数组，对角线元素是每个heights[i]，对角线以下都无意义，对角线以上是每个heights元素左侧最小的元素。剩下的面积的计算就显而易见了。但是TLE at https://leetcode.com/submissions/detail/243324357/testcase/ ，list(range(20000))。

然后思路是sliding window，然而发现每个iteration，左边界和右边界移动的距离不确定。

note3: 图解stack大法的O(n)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights += [0]
        
        area = 0
        stack = []
        for i in range(len(heights)):
            if not stack or heights[stack[-1]] < heights[I]:
                stack.append(i)
            else:
                while heights[stack[-1]] >= heights[I]:
                    h = heights[stack.pop()]
                    if not stack:
                        w = I
                        area = max(w*h,area)
                        break
                    else:
                        w = i - stack[-1] - 1
                    area = max(w*h,area)
                stack.append(i)
                
        return area

Runtime: 60 ms, faster than 86.64% of Python3 online submissions for Largest Rectangle in Histogram.
Memory Usage: 15 MB, less than 42.19% of Python3 online submissions for Largest Rectangle in Histogram.