https://leetcode.com/problems/largest-rectangle-in-histogram/
这种面积问题，遇到过无数次，可以有多种解法。array，stack，线段树等。

个人解答

1. 左右数组解法

  1. class Solution:
  2.     def largestRectangleArea(self, h: List[int]) -> int:
  3.         lessleft = [-1] * len(h)
  4.         for i in range(len(h)):
  5.             p = i - 1
  6.             while p >= 0 and h[i] <= h[p]:
  7.                 p = lessleft[p]
  8.             lessleft[i] = p
  10.         lessright = [len(h)] * len(h)
  12.         res = 0
  13.         for i in range(len(h) - 1, -1, -1):
  14.             p = i + 1
  15.             while p < len(h) and h[i] <= h[p]:
  16.                 p = lessright[p]
  17.             lessright[i] = p
  19.             res = max(res, h[i] * (lessright[i] - lessleft[i] - 1))
  21.         return res

2. stack解法

  1. class Solution:
  2.     def largestRectangleArea(self, H: List[int]) -> int:
  3.         H.append(0) # NOTE: add tail 0, count last one
  4.         stk = [-1]
  5.         res = 0
  6.         for i in range(len(H)):
  7.             while H[i] < H[stk[-1]]:
  8.                 h = H[stk.pop()]
  9.                 w = i - stk[-1] - 1 # NOTE: use current last idx - 1 instead of previous last idx
  10.                 res = max(res, h * w)
  11.             stk.append(i)
  13.         return res

题目分析

第一种解法，思路还是比较清晰的，对于每一个位置，以当前高度为基础，看能延申多少宽度，也就是求两侧距离最近的比它高度小的位置。
从左往右，从右往左各扫一遍即可。
在计算这个更小位置时，可以利用之前计算的结果快速推导，大幅降低复杂度。

第二种解法，就比较难想到了。
一个单调栈的典型应用。
想清楚一个问题，如果碰到一个较小的值，那么之前较大的值是没有念想了，延申就此终止。此时，将这些更大的值，挨个计算他们对应的长方形，然后pop出来就可以了。

注意代码中，计算宽度时候，用的是pop完成之后的前一个的index，因为前一个index和pop出的index之中，可能存在大于pop出idx对应的高度的元素，这些也要被算进宽度里。