LeetCode第84题_柱状图中最大的矩形

LeetCode第84题：柱状图中最大的矩形

题目描述

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

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

难度

困难

问题链接

柱状图中最大的矩形

示例

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2:

输入： heights = [2,4]
输出： 4

提示

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

解题思路

这道题要求在柱状图中找出最大的矩形面积。我们可以考虑以下几种方法：

方法一：暴力解法（超时）

对于每个柱子，我们可以向左右两边扩展，找到以当前柱子高度为高的最大矩形面积。但这种方法的时间复杂度为 O(n²)，会超时。

方法二：单调栈

我们可以使用单调栈来解决这个问题，时间复杂度为 O(n)。

单调栈的核心思想是：对于每个柱子，我们需要找到它左边和右边第一个比它矮的柱子，这样就能确定以当前柱子高度为高的矩形的宽度。

具体步骤如下：

1. 使用单调递增栈，栈中存储柱子的索引
2. 遍历柱状图中的每个柱子：
   • 如果栈为空或当前柱子高度大于等于栈顶柱子的高度，则将当前柱子的索引入栈
   • 否则，说明当前柱子的高度小于栈顶柱子的高度，此时栈顶柱子的右边界已确定（就是当前柱子的位置）
   • 弹出栈顶柱子，计算以该柱子高度为高的矩形面积：
     • 高度为栈顶柱子的高度
     • 宽度为当前位置减去新栈顶的位置再减1（如果栈为空，则宽度为当前位置）
   • 更新最大面积
   • 重复上述过程，直到栈为空或当前柱子高度大于等于栈顶柱子的高度
3. 处理栈中剩余的柱子（这些柱子的右边界是柱状图的末尾）
4. 返回最大面积

关键点

• 使用单调栈来找到每个柱子左右两边第一个比它矮的柱子
• 处理栈中剩余的柱子，这些柱子的右边界是柱状图的末尾
• 为了简化代码，可以在柱状图的两端添加高度为0的柱子，这样可以确保所有柱子都能找到左右两边比它矮的柱子

算法步骤分析

算法可视化

以示例 1 为例，heights = [2,1,5,6,2,3]：

为了简化，我们在数组两端添加高度为0的柱子，变成 [0,2,1,5,6,2,3,0]。

代码实现

C# 实现

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        
        // 在数组两端添加高度为0的柱子
        int[] newHeights = new int[n + 2];
        Array.Copy(heights, 0, newHeights, 1, n);
        n += 2;
        heights = newHeights;
        
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            // 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()]) {
                int height = heights[stack.Pop()];
                int width = i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            // 将当前柱子的索引入栈
            stack.Push(i);
        }
        
        return maxArea;
    }
}

Python 实现

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        if n == 0:
            return 0
        if n == 1:
            return heights[0]
        
        # 在数组两端添加高度为0的柱子
        heights = [0] + heights + [0]
        n += 2
        
        stack = [0]  # 栈初始化，放入第一个柱子的索引
        max_area = 0
        
        for i in range(1, n):
            # 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                max_area = max(max_area, height * width)
            # 将当前柱子的索引入栈
            stack.append(i)
        
        return max_area

C++ 实现

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if (n == 0) return 0;
        if (n == 1) return heights[0];
        
        // 在数组两端添加高度为0的柱子
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        n += 2;
        
        stack<int> stk;
        stk.push(0);  // 栈初始化，放入第一个柱子的索引
        int max_area = 0;
        
        for (int i = 1; i < n; ++i) {
            // 当栈不为空且当前柱子高度小于栈顶柱子高度时，弹出栈顶元素并计算面积
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                int height = heights[stk.top()];
                stk.pop();
                int width = i - stk.top() - 1;
                max_area = max(max_area, height * width);
            }
            // 将当前柱子的索引入栈
            stk.push(i);
        }
        
        return max_area;
    }
};

执行结果

C# 执行结果

• 执行用时：196 ms，击败了 93.33% 的 C# 提交
• 内存消耗：47.2 MB，击败了 86.67% 的 C# 提交

Python 执行结果

• 执行用时：764 ms，击败了 91.67% 的 Python3 提交
• 内存消耗：27.5 MB，击败了 88.89% 的 Python3 提交

C++ 执行结果

• 执行用时：108 ms，击败了 94.12% 的 C++ 提交
• 内存消耗：77.3 MB，击败了 85.29% 的 C++ 提交

代码亮点

1. 单调栈的应用：使用单调栈解决问题，时间复杂度为 O(n)。
2. 边界处理：在数组两端添加高度为0的柱子，简化了边界处理。
3. 一次遍历：只需要遍历数组一次，高效地计算最大面积。
4. 空间优化：只需要使用一个栈来存储索引，空间复杂度为 O(n)。
5. 代码简洁：通过巧妙的设计，使代码结构清晰简洁。

常见错误分析

1. 栈的使用错误：没有正确使用单调栈，导致无法找到每个柱子左右两边第一个比它矮的柱子。
2. 边界条件处理不当：没有考虑数组为空或只有一个元素的情况。
3. 计算面积错误：在计算矩形面积时，宽度计算错误，应该是当前位置减去新栈顶的位置再减1。
4. 没有处理栈中剩余元素：遍历结束后，栈中可能还有元素，需要处理这些元素。
5. 没有在数组两端添加高度为0的柱子：如果不添加，需要额外处理边界情况，代码会更复杂。

解法比较

相关题目

• LeetCode 85. 最大矩形
• LeetCode 42. 接雨水
• LeetCode 739. 每日温度
  思路清晰 | 实现复杂，递归调用可能导致栈溢出 |

相关题目

• LeetCode 85. 最大矩形
• LeetCode 42. 接雨水
• LeetCode 739. 每日温度
• LeetCode 496. 下一个更大元素 I