延吉最好的网站建设公司,个人网站用什么服务器,有哪些游戏网站,深圳高端做网站84. 柱状图中最大的矩形 给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。 求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。 class Solution:def largestRectangleArea(self, heights: List[int]) - i…84. 柱状图中最大的矩形 给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。 求在该柱状图中能够勾勒出来的矩形的最大面积。 class Solution:def largestRectangleArea(self, heights: List[int]) - int:找每个柱子左右侧的第一个高度值小于该柱子的柱子单调栈栈顶到栈底从大到小每插入一个新的小数值时都要弹出先前的大数值栈顶栈顶的下一个元素即将入栈的元素这三个元素组成了最大面积的高度和宽度情况一当前遍历的元素heights[i]大于栈顶元素的情况情况二当前遍历的元素heights[i]等于栈顶元素的情况情况三当前遍历的元素heights[i]小于栈顶元素的情况# 栈头到栈底单调递减# 栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度heights.insert(0,0)heights.append(0)stack [0]result 0for i in range(1,len(heights)):# 情况一if heights[i] heights[stack[-1]]:stack.append(i)# 情况二elif heights[i] heights[stack[-1]]:stack.pop()stack.append(i)# 情况三else:# 抛出所有较高的柱子while stack and heights[i] heights[stack[-1]]:# 栈顶就是中间的柱子主心骨mid_index stack[-1]stack.pop()if stack:left_index stack[-1]right_index iwidth right_index - left_index -1height heights[mid_index]result max(result,width*height)stack.append(i)return result
