https://leetcode.cn/problems/0ynMMM/description/
一、题目解析
1.1 题意
给一个非负整数数组 heights，每个元素表示柱状图中一根宽度为 1 的柱子高度。求能勾勒出的最大矩形面积。
plain text
输入：heights = [2,1,5,6,2,3]输出：10最大矩形由高度 5 和 6 的两根柱子并排构成：高 5（受限于较矮的那根）、宽 2，面积 10。
1.2 核心问题
一根柱子能"撑起"多大的矩形，取决于它向左右能延伸到多远——碰到第一个比自己矮的柱子就得停下。
以 heights = [2,1,5,6,2,3] 为例。heights[2] = 5 向左找第一个更矮的柱子，是下标 1 处高度为 1 的那根；向右找，是下标 4 处高度为 2 的那根。以 5 为高的矩形最多能跨 2 个格子（下标 2 和 3），宽 = 4 - 1 - 1 = 2，面积 = 5 × 2 = 10。
其他柱子也各有一块以自己为高的最大矩形，遍历取最大值即为答案。问题的本质是对每根柱子找左右第一个更小元素的下标——单调栈的经典场景。
二、单调栈模板
2.1 基本模板
单调栈的核心用途：O(n) 时间找到每个元素左侧/右侧第一个比它大（或小）的元素。
以"下一个更小元素"为例，栈内维护下标，对应的元素值从栈底到栈顶严格递增：
java
Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < n; i++) { while (!stack.isEmpty() && arr[stack.peekLast()] > arr[i]) { int idx = stack.pollLast(); // arr[idx] 的右侧第一个更小元素是 arr[i] int left = stack.isEmpty() ? -1 : stack.peekLast(); // left 是 arr[idx] 的左侧第一个更小元素的下标 // 左右边界同时到手，在此结算 } stack.addLast(i);}当前元素 arr[i] 比栈顶元素小时，栈顶的"右侧第一个更小元素"出现了——弹出栈顶来结算。弹出后新栈顶就是它的"左侧第一个更小元素"（单调递增栈的性质：栈内每个元素都严格小于它后面入栈的元素）。
2.2 弹栈拿到的三个值
弹栈时获取3个信息：
- 被弹下标：当前要结算的柱子
- 左边界（弹完后
stack.peekLast()）：左侧第一个更小元素的下标 - 右边界（当前
i）：右侧第一个更小元素的下标
矩形面积 = arr[被弹下标] × (右边界 - 左边界 - 1)。
三、哨兵设计
3.1 边界问题
- 栈弹空后，
peekLast()抛异常——左边界不存在 - 遍历结束后，栈里剩的元素没被弹出——这些位置右侧没有更小的值，矩形面积未结算
解题思路：在数组首尾各补一个高度为 0 的哨兵。
3.2 哨兵代码
java
int n = heights.length;int[] extended = new int[n + 2];System.arraycopy(heights, 0, extended, 1, n);// extended[0] = 0（左哨兵），extended[n + 1] = 0（右哨兵）- 左哨兵高度 0，比所有真实柱子都矮，永远不会被弹出。栈里至少始终有它，
peekLast()永远不空。 - 右哨兵高度 0，遍历到它时，所有真实柱子的高度都比 0 大，触发 while 条件把栈内剩余元素全部弹出结算。
加了哨兵后，不需要任何 isEmpty() 判断和边界特判，代码路径统一。
四、完整代码
java
class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; // 首尾各补一个高度为 0 的哨兵，避免空栈和剩余元素未结算 int[] extended = new int[n + 2]; System.arraycopy(heights, 0, extended, 1, n); // 单调递增栈，存下标。左哨兵 0 先入栈 Deque<Integer> stack = new ArrayDeque<>(); stack.addLast(0); int maxArea = 0; // 从 1 开始（下标 0 是左哨兵），走到 n+1（右哨兵），全部结算 for (int i = 1; i < extended.length; i++) { // 当前高度 < 栈顶高度 → 栈顶的右边界出现，弹出并结算面积 while (extended[stack.peekLast()] > extended[i]) { int hIdx = stack.pollLast(); // 被弹出的柱子下标 int h = extended[hIdx]; // 矩形高度 int left = stack.peekLast(); // 左边界：弹完后栈顶 int w = i - left - 1; // 矩形宽度 maxArea = Math.max(maxArea, h * w); } stack.addLast(i); } return maxArea; }}关键点：
stack.peekLast()拿左边界在pollLast()之后执行——被弹元素已出栈，新栈顶就是左侧第一个比它矮的位置- 宽度
i - left - 1：右边界i处的柱子在矩形之外，左边界left处的柱子也在矩形之外，中间的柱子才属于这个矩形 extended[stack.peekLast()] > extended[i]用严格大于，相等时不弹出——等高的柱子合并处理，宽度叠加到第一次弹出的那个高度上
复杂度：O(n) 时间。扩展数组和栈各 O(n) 空间。