一、柱状图中最大的矩形
1.1 题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=10^50 <= heights[i] <= 10^4
1.2 题目链接
84.柱状图中最大的矩形
1.3 解题思路和过程想法
（1）解题思路
思路：
以当前列为高度的矩形，需找到左右第一个比其矮的两个列，以两个列之间的距离（不包括这两列）为宽度，高度*宽度=以当前列为高度的矩形大小。要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置--->单调栈
细节：
# 若数组出现单调增，则会一直入栈，不会有结果，此时需在结尾加一个 0
# 若数组出现单调减，则会一直出栈，为有统计结果，此时需在起始处加一个 0
upStack = [0] # 赋有初始值，保证只有两个数时也可计算
# 当前数大于栈顶数---》压栈
# 当前数等于栈顶数-------》先弹栈，后压栈（若连续出现相等，为不重复，只计算一次）
# 当前数小于栈顶数：当前（小） 栈顶（中） 栈顶内侧（小），按照思路统计矩形面积
（2）过程想法
构思矩形的计算方式才是关键
我对于栈的单调性有自己的理解，我不记固定的单调关系：
若要找左侧或右侧第一个比栈顶元素都大的元素，就将比它小的都压栈，直到遇到比栈顶元素大的元素
若要找左侧或右侧第一个比栈顶元素都小的元素，就将比它大的都压栈，直到遇到比栈顶元素小的元素
1.4 代码
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 接雨水是不用统计第一个和最后一个节点，但此处需要思考
# 若数组出现单调增，则会一直入栈，不会有结果，此时需在结尾加一个 0
# 若数组出现单调减，则会一直出栈，为有统计结果，此时需在起始处加一个 0
if len(heights) == 1:
return heights[0]
heights.insert(0,0)
heights.append(0)
length = len(heights)
upStack = [0] # 赋有初始值，保证只有两个数时也可计算
res = 0
for i in range(1,length):
if len(upStack) == 0 or heights[i] >= heights[upStack[-1]]: # 当前数大于栈顶数
upStack.append(i)
elif len(upStack) == 0 or heights[i] >= heights[upStack[-1]]: # 当前数等于栈顶数-------》若连续出现相等，为不重复，只计算一次
upStack.pop()
upStack.append(i)
else:
while len(upStack) and heights[i] < heights[upStack[-1]]: # 当前数小于栈顶数：当前（小） 栈顶（中） 栈顶内侧（小）
mid = heights[upStack[-1]]
upStack.pop()
if len(upStack) > 0:
left = upStack[-1]
right = i
h = mid
w = right - left - 1
res = max(res, h*w)
upStack.append(i)
return res
