這題感到棘手，寫好的暴力破解法會超時，只能不斷看題目去領悟點甚麼。
找出最大面積不是件難事，要怎麼才能加速呢？
看了搜尋的兩前項，別人寫著遞增數列，找局部峰值，為什麼？到底有甚麼關係？
我簡單一句講明目的：「把這張直方圖分切出各個好處理的部分。」
在這個遞迴II章節，有一個部分是在說到把問題切碎，處理後再重組，得到答案。這就是需要這樣做的例子。
 |
| 直方圖分解示意圖 |
把局部峰值也就是左大右小之處，切下去，左邊的值會遞減。得到一個遞增數列再往右搜尋。
碰到下一個峰值，往左遇到實際較高的直方，因為它已經被切進上一個遞增數列，所以可以忽視掉突出部分，維持一樣的值繼續遞減。
一旦變成遞增數列就可以很快速地找到最大面積。
把直方圖的每直方看成座標，遞增數列的右下角為原點，找出端點x和y絕對值相乘最大的就是該部分最大面積。
得到各部分的最大面積，再相互比較，就能得到直方圖中最大的長方形面積。
class Solution:
"""遞增數列"""
def largestRectangleArea(self, heights) -> int:
if not heights: return 0
peaks = []
p = None
for idx, each in enumerate(heights):
if p and each < p:
peaks.append(idx-1)
p = each
peaks.append(n-1)
maxAreas = []
while peaks:
# 從右而左搜尋
endpoint = peaks.pop()
height = heights[endpoint]
maxArea = 0
for i in range(endpoint,-1,-1):
width = endpoint+1-i
height = min(height, heights[i])
maxArea = max(maxArea, width*height)
maxAreas.append(maxArea)
return max(maxAreas)
先找峰值，紀錄峰值出現在哪，最後一個也是峰值，最後從記錄找起一次把各種切出遞增數列找出最大長方形面積，再得到當中的最大值。接下來就是優化了，對於一個 N 個數列，首先先減少遍例次數，求各遞增數列的最大面積可以放在找峰值的時候進行。
而且如果左右兩個點一樣高，可以忽略右邊的不計，減少要找的端點。在遍歷各端點時，如果剩下的最大可能面積沒辦法比較大，就可以跳出迴圈。
經過一番優化之後，就變成這樣。
這讓我深刻體會到，unfold 的好處在哪裡。如果沒有標上註解，可讀性遠遠不如上一個。
class Solution:
"""遞增數列"""
def largestRectangleArea(self, heights) -> int:
if not heights: return 0
def getMaxArea():
area = 0
endpoint, height = hArray.pop()
for i in range(len(hArray)-1,-1,-1):
idx, h2 = hArray[i]
width = endpoint+1-idx
height = min(height, h2)
area = max(area, width*height)
if (endpoint+1)*height <= area:break
return area
n = len(heights)
hArray= []
maxAreas = []
for idx, h in enumerate(heights):
if idx:
if h < preH: #出現峰值，即刻求該遞增數列的最大面積
# 添加EndPoint
hArray.append((idx-1, preH))
# 搜尋當前面積
maxAreas.append(getMaxArea())
# 砍掉前面鋒值凸出的部分，最後要添加端點紀錄修改
stack = [idx, h]
while hArray and hArray[-1][1] > h:
stack[0] = hArray[-1][0]
del hArray[-1]
hArray.append(stack)
elif h > preH: #紀錄遞增變化
hArray.append((idx, h))
else:
hArray.append((idx, h))
preH = h
# 最後一搜,其中一個為最後一直方的左上端點 另一個是右上
hArray.extend([(idx, h), (idx, h)])
maxAreas.append(getMaxArea())
return max(maxAreas)