73.柱状图中最大的矩形

LCR 039. 柱状图中最大的矩形

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

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

示例 1:

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

核心思路是找到每个柱子左右两侧第一个更矮的柱子，从而确定该柱子能构成的最大矩形宽度。

对于每个柱子 heights[i]，能构成的最大矩形面积 = heights[i] × 宽度，其中：

• 宽度 = 右侧第一个更矮柱子的下标 - 左侧第一个更矮柱子的下标 - 1
• 如果左侧没有更矮的柱子，左边界记为 -1；如果右侧没有更矮的柱子，右边界记为 数组长度

【大的直接入栈，小的再去计算】

关键在于宽度的计算

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length;int maxArea = 0;// 单调栈：存储下标，保证栈内下标对应的高度单调递增Deque<Integer> stack = new ArrayDeque<>();// 遍历每个下标（包括虚拟的"右边界"n）for (int i = 0; i <= n; i++) {// 当i==n时，高度视为0（触发栈内剩余元素的计算）int currHeight = (i == n) ? 0 : heights[i];// 当前高度 < 栈顶下标对应的高度 → 栈顶元素的右边界是i，左边界是新栈顶while (!stack.isEmpty() && currHeight < heights[stack.peek()]) {int topIndex = stack.pop(); // 弹出栈顶（要计算的柱子下标）int height = heights[topIndex]; // 该柱子的高度// 计算宽度：栈空则左边界是-1，否则是新栈顶下标int width = stack.isEmpty() ? i : (i - stack.peek() - 1);int area = height * width; // 计算面积maxArea = Math.max(maxArea, area); // 更新最大面积
            }stack.push(i); // 当前下标入栈
        }return maxArea;}
}

【背吧，绕得很】