网站建设明细报价,最新国际新闻头条新闻,企业管理平台软件,微客通达推广引流84.柱状图中最大的矩形
力扣题目链接(opens new window)
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的最大面积。 1 heights.length 10^50 hei…84.柱状图中最大的矩形
力扣题目链接(opens new window)
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。 1 heights.length 10^50 heights[i] 10^4 初始化栈和最大面积变量: 创建一个空栈 stack 来存储柱子的索引。初始化一个变量 max_area 用于存储遍历过程中计算出的最大面积。 处理每个柱子: 遍历每个柱子的高度 heights同时在 heights 的末尾添加一个高度为 0 的柱子以确保栈中的所有柱子都能被处理。对于每个柱子 i 当栈不为空且当前柱子的高度 heights[i] 小于栈顶柱子的高度时执行以下操作 弹出栈顶元素该元素索引记为 top。这意味着以 heights[top] 为高的矩形的右边界已经确定。计算矩形的宽度 如果栈为空宽度即为当前柱子的索引 i因为左边界是起始位置。如果栈不为空宽度为 i - stack[-1] - 1当前索引减去新的栈顶元素索引减去1表示两个柱子间的距离。计算矩形面积heights[top] * 宽度并更新 max_area。将当前柱子索引 i 压入栈中。 返回最大面积: 经过上述遍历我们已经计算出了每个可能的矩形的面积并记录了其中的最大值。返回 max_area 作为结果。 class Solution:def largestRectangleArea(self, heights):stack []max_area 0heights.append(0) # 添加一个高度为0的柱子确保所有柱子都被弹出for i, h in enumerate(heights):while stack and heights[stack[-1]] h:height heights[stack.pop()]width i if not stack else i - stack[-1] - 1max_area max(max_area, height * width)stack.append(i)return max_area# solution Solution()
# example_heights [2, 1, 5, 6, 2, 3]
# result solution.largestRectangleArea(example_heights)
# print(result)
