为了做lc85特意先做一下这个题来复习复习单调栈。首先是用暴力算法，对于每个位置，都分别向左向右延伸一下找到比当前位置小的第一个高度，记录前一个位置，同时找到左边和右边的边界后就计算一次面积，将改面积与之前记录的面积比较从而得到答案。这样做的时间复杂度为O（N^2），空间复杂度为O（1）。
考虑用空间换时间，用单调栈的做法。首先考虑，我们在用单调栈的时候记录的是什么信息。如果仅仅记录高度，那么是不够的，因为计算矩形还需要宽度，所以我们应该在栈内记录下标。我们拿数组[2, 1, 5, 6, 2, 3]为例。1.一开始看到的柱形高度为2，这个时候以2为高度的最大面积的矩形还不能确定，我们需要继续向右遍历。2.然后我们看到高度为1的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的，但是它之前的以2为高度的最大面积的矩形可以确定，这是因为1比2小，因为卡在了1这里所以之前的2不能再向右边拓展了。我们计算一下以2为高度的最大矩形的面积是2。3.遍历到高度为5的柱形时，同样的以当前看到的柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么是否和第2步中一样在它左右有没有可以确定的柱形呢？答案是没有，这是因为5比1大，我们看后面马上就出现了6，不管是1这个柱形还是5这个柱形都可以继续向右边拓展。4.接下去，遍历到高度为6的柱形，同样的，以柱形1、5、6为高度的最大矩形面积还是不能确定下来。5.再接下去，遍历到高度为2的柱形，我们发现此时高度为6的柱形对于的最大矩形的面积的宽度可以确定下来了，它就是夹在高度为5的柱形和高度为2的柱形之间的距离，它的高度是6，宽度为1。并且，柱形5对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为1和高度为2的两个柱形之间的距离。
从上面的步骤我们发现，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边到左边。这个现象告诉我们，在遍历的时候需要记录的信息是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。此时，我们还要考虑另外一个细节，在确定一个柱形面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。那如果是左边的高度和自己相等怎么办呢？其实我们也还不能确定。总之，我们在遍历是记录下标，如果当前高度比它之前的高度严格小于的时候，就可以字节确定之前的那个高的柱形的最大矩形的面积，为了确定这个最大矩形的左边界，我们还需要在向左回退的时候找到第一个严格小于它的高度的矩形。
我们发现，我们想确定6的宽度时候，6的宽度确定完了我们就不需要它了，当5的高度和5的宽度确定确定完我们也不需要它了。我们在缓存数据的时候，上从左向右缓存的，我们计算出一个结果的顺序是从右向左的，并且计算完以后我们就不需要了，符合后进先出的特点。因此我们需要的作为缓存的结构就是栈。当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次出栈一次，一开始栈为空最后也要为空，表示这个高度数组里所有的元素都考虑完了。6.最后遍历到最后一个柱形，和之前的步骤一样，只不过现在右边没有比它高度还小的柱形了，这个时候计算宽度应该假设最右边还有一个下标为len（这里为6）的高度为0的柱形。7.下标为5即高度为3的柱形，左边的下标是4，右边的下标是6，因此宽度是6-4-1=1。8.往回走，下标为4高度为2的柱形，左边的下标为1右边的下标为6，因此宽度是6-1-1=4。9.最后看下标为1，高度为1的矩形，它的左边右边其实都没有元素了，它就是整个数组里最低的柱形，计算它的宽度也就是整个数组的长度。至此所有的柱形高度对于的最大矩形的面积就算出来了。这个算法经过一次遍历，在每次计算最大宽度的时候没有去遍历而是使用了栈里存放的下标信息，以O（1）的时间复杂度计算最大宽度。
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
以上这个算法要考虑两种特殊情况：1.弹栈的时候，栈为空。2.遍历完成后，栈中还有元素。为此我们可以在数组的两端加上两个高度为0的柱形，它们可以回避上面这两种分类讨论。这两个在两边的柱形有一个很形象的名词，叫做哨兵（Sentinel）有了这两个柱形后：1.左边的柱形由于它一定比输入数组里的任何一个元素小，它肯定不会出栈，因此栈一定不会为空。2.右边的柱形也因为它一定比输入数组的任何一个元素小，它会让所有元素出栈（除了新加的左边的哨兵外）。另外，实现3写的是不用哨兵的，这样更容易泛化到别的题型上面。
ps. 后续在对哨兵的使用做了一个小改变，使得代码更简介了。如4所示。
python:
from typing import List
class Solution:
def largestRectangleArea1(self, heights: List[int]) -> int:
size = len(heights)
res = 0
for i in range(size):
left = i
cur_height = heights[i]
while left > 0 and heights[left - 1] >= cur_height:
left -= 1
right = i
while right < size -1 and heights[right + 1] >= cur_height:
right += 1
max_width = right - left + 1
res = max(res, max_width * cur_height)
return res
def largestRectangleArea2(self, heights: List[int]) -> int:
res = 0
heights = [0] + heights + [0]
stack = [0]
size = len(heights)
for i in range(1, size):
while heights[i] < heights[stack[-1]]:
cur_height = heights[stack.pop()]
cur_width = i - stack[-1] - 1
res = max(res, cur_height * cur_width)
stack.append(i)
return res
def largestRectangleArea3(self, heights: List[int]) -> int:
size = len(heights)
res = 0
stack = []
for i in range(size):
while len(stack) > 0 and heights[i] < heights[stack[-1]]:
cur_height = heights[stack.pop()]
while len(stack) > 0 and cur_height == heights[stack[-1]]:
stack.pop()
if len(stack) > 0:
cur_width = i - stack[-1] - 1
else:
cur_width = i
res = max(res, cur_height * cur_width)
stack.append(i)
while len(stack) > 0 is not None:
cur_height = heights[stack.pop()]
while len(stack) > 0 and cur_height == heights[stack[-1]]:
stack.pop()
if len(stack) > 0:
cur_width = size - stack[-1] - 1
else:
cur_width = size
res = max(res, cur_height * cur_width)
def largestRectangleArea4(self, heights: List[int]) -> int:
res = 0
heights = heights + [0]
stack = [-1]
size = len(heights)
for i in range(size):
while heights[i] < heights[stack[-1]]:
cur_height = heights[stack.pop()]
cur_width = i - stack[-1] - 1
res = max(res, cur_height * cur_width)
stack.append(i)
return resC++: