084-柱状图中最大的矩形

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

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

思路：单调递增栈 + 哨兵技巧

• 核心思想：对于每个柱子，找出以它为最矮高度时能形成的最大矩形。
• 用单调递增栈（存下标）维护”还没找到右边界”的柱子。
• 当遇到更矮的柱子时，说明栈顶柱子的右边界确定了，可以结算面积。
• 在数组末尾添加高度为 0 的哨兵，确保所有柱子都能被结算。

时间复杂度 (O(n))，每个下标最多入栈、出栈各一次。

代码实现

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;

        // 新数组：末尾加一个高度为 0 的哨兵，用来触发最终清算
        int[] newArray = new int[len + 1];
        System.arraycopy(heights, 0, newArray, 0, len);
        newArray[len] = 0;

        int ans = 0;
        // 单调递增栈：存下标，保证 newArray[栈底..栈顶] 递增
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i <= len; i++) {
            int cur = newArray[i];

            // cur 更矮：说明 cur 是"栈顶柱子"右侧第一个更矮柱子，栈顶柱子的右边界确定，可结算面积
            while (!stack.isEmpty() && newArray[stack.peek()] > cur) {
                int mid = stack.pop();
                int height = newArray[mid]; // 以 mid 为最矮高度

                // leftLess：mid 左侧第一个更矮柱子的下标；若不存在，用 -1 表示边界外
                int leftLess = stack.isEmpty() ? -1 : stack.peek();

                // 宽度 = 右边界(i-1) - 左边界(leftLess+1) + 1 = i - leftLess - 1
                int width = i - leftLess - 1;

                ans = Math.max(ans, height * width);
            }

            // 入栈，维持单调递增（等待将来遇到更矮柱子时结算）
            stack.push(i);
        }

        return ans;
    }
}

数组复制方法

System.arraycopy（最常用、最快、底层优化）

适合：把一个数组的一段复制到另一个数组（包括扩容后复制）

int n = heights.length;
int[] a = new int[n + 1];
System.arraycopy(heights, 0, a, 0, n);
a[n] = 0; // 哨兵

• 复制的是元素引用/值（int 是值）
• 对对象数组是浅拷贝（只拷引用）

Arrays.copyOf（最适合”扩容复制”）

适合：刷题里最常见的”复制并扩到新长度”

import java.util.Arrays;

int[] a = Arrays.copyOf(heights, heights.length + 1);
a[heights.length] = 0;

• 简洁、语义清晰
• 内部也会用高效复制