代码随想录——柱状图中最大的矩形（Leetcode 84）

题目链接

我的解法（暴力）

果不其然，超时是暴力解法的宿命…
双层for循环真的很好懂，每次解题都感觉我应该是一个单细胞生物…

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        for(int i = 0; i < heights.length; i++){
            int commonHeight = heights[i];
            max = Math.max(max, commonHeight);
            for(int j = i + 1; j < heights.length; j++){
                commonHeight = Math.min(commonHeight, heights[j]);
                max = Math.max(max, commonHeight * (j - i + 1));
            }
        }
        return max;
    }
}

优秀题解

单调栈
思路：

1. 初始化：定义一个栈 stack 用来存储柱子的索引，一个变量 max 用来记录遍历过程中计算出的最大矩形面积。

2. 遍历数组：通过一个 for 循环遍历每个柱子的高度 heights[i]。

3. 维护栈的单调递减：在处理每个柱子时，如果栈不为空且当前柱子的高度小于栈顶柱子的高度，这意味着我们可以计算栈顶柱子能构成的矩形面积了。因为只有更矮的柱子才能限制栈顶柱子的宽度。计算方法是：

   • 弹出栈顶柱子的索引，得到其高度 h。
   • 计算宽度 w：如果栈为空，说明栈顶柱子的左边没有柱子了，宽度就是当前索引 i；否则，宽度是当前索引 i 减去栈顶索引减去 1（因为栈顶索引包含在内）。
   • 更新 max 为当前计算的矩形面积和已有最大值中的较大者。

4. 处理当前柱子：将当前柱子的索引 i 压入栈中。

5. 处理剩余柱子：在数组遍历完成后，栈中可能还有一些柱子没有处理。这些柱子可以看作是到达了数组的末尾，因此它们的宽度是数组的长度减去栈顶索引再减去 1。

这个算法的关键在于利用栈来维护一个单调递减的序列，这样可以在遍历数组的过程中找到每个柱子的最大矩形面积。算法的时间复杂度是 O(n)，其中 n 是数组 heights 的长度。

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for(int i = 0; i < heights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int h = heights[stack.pop()];
            int w = stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1;
            max = Math.max(max, h * w);
        }
        return max;
    }
}