代码随想录算法训练营Day 60 || 84.柱状图中最大的矩形

84.柱状图中最大的矩形

力扣题目链接(opens new window)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

1. 初始化栈和最大面积变量:

   • 创建一个空栈 stack 来存储柱子的索引。
   • 初始化一个变量 max_area 用于存储遍历过程中计算出的最大面积。

2. 处理每个柱子:

   • 遍历每个柱子的高度 heights，同时在 heights 的末尾添加一个高度为 0 的柱子，以确保栈中的所有柱子都能被处理。
   • 对于每个柱子 i：
     • 当栈不为空且当前柱子的高度 heights[i] 小于栈顶柱子的高度时，执行以下操作：
       • 弹出栈顶元素，该元素索引记为 top。这意味着以 heights[top] 为高的矩形的右边界已经确定。
       • 计算矩形的宽度：
         • 如果栈为空，宽度即为当前柱子的索引 i（因为左边界是起始位置）。
         • 如果栈不为空，宽度为 i - stack[-1] - 1（当前索引减去新的栈顶元素索引，减去1表示两个柱子间的距离）。
       • 计算矩形面积：heights[top] * 宽度，并更新 max_area。
     • 将当前柱子索引 i 压入栈中。

3. 返回最大面积:

   • 经过上述遍历，我们已经计算出了每个可能的矩形的面积，并记录了其中的最大值。
   • 返回 max_area 作为结果。

class Solution:
    def largestRectangleArea(self, heights):
        stack = []
        max_area = 0
        heights.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] - 1
                max_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)