84.直方图中最大的矩形来源：力扣(LeetCode)https://leetcode-cn.com/problems/largest-rectangle-in-histogram/题目给出了n个非负整数，用来表示每一个的高度直方图中的列。每列彼此相邻，宽度为1。找出直方图中可以勾勒出的矩形的最大面积。以上是条形图的示例，其中每个条形的宽度为1，高度为[2,1,5,6,2,3]。图中阴影部分为最大可绘制的矩形区域，其面积为10个单位。例子：输入：[2,1,5,6,2,3]输出：10解题思路：栈在讲栈之前，先说说暴力解这道题怎么解。题目中要求我们找出最大的可以勾勒出轮廓的矩形区域。其实求矩形区域有两种方法：固定宽度，改变高度，求最大面积，固定高度，改变宽度，求最大面积。在这道题中，使用第二种这种方法更容易得到结果。如何实现？这里，我们依次遍历列的高度，然后将每个高度向两侧展开（当左右遇到列高小于当前列高的列时，将无法继续展开）从而找到当前高度可以展开的最大宽度。得到宽度后，就可以得到面积了。依次比较每个柱高处扩散最大的面积，最后确定最大面积。这里Python在使用暴力破解的时候会超时，所以这里就不给出代码了。（不过还是建议个人尝试写一下）我们在使用暴力解的时候，遍历的时候需要从中间开始扩散。这里，时间复杂度是O(n^2)，空间复杂度是O(1)，因为只有常数变量。那么我们可以考虑在遍历的时候，利用【空间换时间】的思想来记录一些信息。这里，注意上面用黑色字体标注的内容，【当左右遇到一个列高小于当前列高的列时，则无法继续传播】，这里我们可以认为问题的关键是在左右两边分别找到比当前bar高度小的bar，这样宽度就可以确定了。这里我们构造一个单调栈。单调栈：分为单调递增栈和单调递减栈。单调递增栈，栈中元素保持单调递增单调递减栈，栈中元素保持单调递减小时，弹出栈中元素，直到栈顶元素小于新元素。我们看例子，[2,1,5,6,2,3]我们建了一个栈，里面存放的是数组中的索引。结合上面的图例，这里，假设我们现在索引指向的元素是6（此时栈中对应的索引是156），下一个元素是2，按照栈单调递增的操作，这里需要出栈6，所以2是这个元素之后第一个比它小的元素。当元素出栈时，栈顶元素是第一个比它之前出栈元素小的元素，此时为5。这时候就可以确定高度为6的列的宽度了。,面积也可以确定。同理，此时栈顶索引对应的元素为5，也小于2，需要出栈。此时栈顶对应的元素为1（和上面的逻辑一样，这是之前的栈元素的第一个索引是小元素），那么宽高为5就可以了确定，也就是元素1和元素2之间的宽度。按照这个逻辑，具体实现思路：建立一个单调递增的栈，遍历大于栈顶元素的元素，如果遍历到的元素小于栈顶元素栈顶元素，出栈时，判断宽度，求面积。具体实现代码如下。代码实现类Solution:deflargestRectangleArea(self,heights:List[int])->int:size=len(heights)#这里使用sentinel节点，避免非空判断heights=[0]+heights+[0]#数组长度发生了变化size+=2#先将sentinel入栈stack=[0]ans=0foriinrange(1,size):#与栈顶元素比较判断是否进入Stack#pop逻辑whileheights[i]
