## 单调栈 1. 为什么用单调栈 2. 维护单调栈单调的基准是什么 3. 单调栈内存储的内容是什么 4. 如何利用单调栈中的内容，配合待入栈的元素，勾勒出矩形 ```python class Solution: def largestRectangleArea(self, heights: List[int]) -> int: # 单调栈 # 为了方便找到左边第一个小和右边第一个小，'栈底到栈顶'应该保持'高度值'的单调递增 # 这样对于栈顶元素，栈顶的下一个元素就是左边第一个小的元素。而待检查入栈的可能是右边第一个小。 # 这样就就可以勾勒出以栈顶元素为高度值的矩形了。 st = [] ans = 0 # > 对于Case:[2,4] 由于递增的 始终与不到右边第一个小的元素 无法开始计算面积 预处理一下。 heights.append( 0 ) # > 对于Case:[1,1] 找不到左边第一个小的元素 无法开始计算面积 与处理一下。 heights.insert( 0, 0 ) for i, v in enumerate( heights ): # 保证栈顶元素大于栈内元素 # 这样栈顶元素的下一个元素就是左边第一个小于栈顶的元素 # 而v < heights[ st[ -1 ] ], v就是栈顶元素右边第一个小的元素 while st and v < heights[ st[ -1 ] ]: h = heights[ st.pop() ] if st: lIdx = st[ -1 ] rIdx = i w = rIdx - lIdx - 1 ans = max( ans, h * w ) st.append( i ) return ans ``` ## 左右第一个小求最大面积 1. 对于左右第一个小的求法，可以积累一下。 ```python class Solution: # 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 # 求在该柱状图中，能够勾勒出来的矩形的最大面积。 # Case1: [2,1,5,6,2,3] # Case2: [2,4] # Case3: [1,1] def largestRectangleArea(self, heights: List[int]) -> int: # 以heights中每一个值作为围成矩形的高 取能够围成矩形的最大值 # 这样的话,就需要记录heights[ i ]左右两边第一个小于heights[ i ]的位置,以确定width n = len( heights ) left_first_less = [ -1 for _ in range( n ) ] right_first_less = [ n for _ in range( n ) ] # 1 <= heights.length <=10e5 很担心记录左右第一个更大的时候超时 # 所以下面做了一个优化, 对于t的复制。由于height[ t ] >= heights[ i ], # 所以heights[ t ]左边第一个小于其的值也小于或大于或等于heights[ i ] # 所以可以直接优化这里的赋值。这是不超时的关键。 for i in range( 1, n ): t = i - 1 while t >= 0 and heights[ t ] >= heights[ i ]: t = left_first_less[ t ] left_first_less[ i ] = t for i in range( n - 2, -1, -1 ): t = i + 1 while t <= n - 1 and heights[ t ] >= heights[ i ]: t = right_first_less[ t ] right_first_less[ i ] = t ans = 0 for i in range( n ): h = heights[ i ] w = right_first_less[ i ] - left_first_less[ i ] - 1 ans = max( ans, h * w ) return ans ```