Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0125-preview· OpenAIAi2 WildChat-4.8M (AI2)

编程题:给定n个非负整数,用来表示柱状图中各个柱子的高度,每个柱子彼此相邻,宽度为1,求该柱状图能勾勒出的矩形的最大面积

  1. User

    编程题:给定n个非负整数,用来表示柱状图中各个柱子的高度,每个柱子彼此相邻,宽度为1,求该柱状图能勾勒出的矩形的最大面积

  2. Assistant

    要解答这个问题,可以通过使用单调栈的方法。单调栈可以帮助我们找到每个柱子左右两边第一个比它短的柱子的位置,从而计算以每个柱子为高的矩形的最大宽度,进而求出面积。

    下面是一个使用单调栈方法的Python代码示例:

    def largestRectangleArea(heights):
        # 在原有高度列表首尾分别添加高度为0的柱子,便于处理边界情况
        heights = [0] + heights + [0]
        stack = []  # 栈中存放柱子的索引
        max_area = 0
    
        for i, height in enumerate(heights):
            # 当栈不为空且当前柱子的高度小于栈顶柱子的高度时,计算以栈顶柱子为高度的矩形面积
            while stack and heights[stack[-1]] > height:
                cur_height = heights[stack.pop()]
                # 由于首尾添加了高度为0的柱子,栈中至少有一个元素,故不需要检查栈是否为空
                width = i - stack[-1] - 1
                max_area = max(max_area, cur_height * width)
            stack.append(i)  # 将当前柱子的索引入栈
    
        return max_area
    
    # 测试代码
    if __name__ == "__main__":
        heights = [2, 1, 5, 6, 2, 3]
        print(largestRectangleArea(heights))
        # 输出应该是10, 由高度为2的柱子(索引4、5)构成的宽为5的矩形
    

    这段代码首先在heights数组的首尾各添加了一个高度为0的柱子,这样做是为了简化代码,避免特殊处理栈为空的情况。然后遍历heights数组,对于每个柱子,使用单调递增栈来找到左边和右边第一个比当前柱子矮的柱子,这样就可以计算出以当前柱子为高的矩形的最大宽度,从而计算出面积。在计算过程中记录并更新最大面积max_area。

    这个方法的时间复杂度是O(n),因为每个元素最多入栈一次,出栈一次。空间复杂度也是O(n),用于存储栈。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.