5.柱状图的最大面积

• 2.24

  • with 想到了，但是面积放错了，放在 while 的外面了

• 2.14

  • 备份一个尾部为 0 的数组，用于对比 length-1 的位置
  • 单调栈永远是递增的，弹出时会永久弹出
  • 宽度为 i-stack。peek（）-1，因为 i 的位置是左边目前最高位置的下标，因为 while 循环，peek 会一直弹出到低于当前位置高度的前一个位置

• 2.2

  • 先备份新的，然后看栈顶（位置）来记录高和宽，尝试更新
  • 不管怎样都 push 当前位置

• 2.1

  • 维护一个单调栈，当，当前的高度小于单调栈栈顶的元素时，弹出栈顶元素作为高，然后根据情况找宽度，尝试更新面积

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public int largestRectangleArea(int[] heights) {
        // 1. 新建一个数组，长度比原数组大 1 (或者大 2，头尾各加一个 0)
        // 这里采用只在末尾加 0 的写法，比较通用
        int n = heights.length;
        int[] newHeights = new int[n + 1];
        
        // 拷贝原数组，newHeights 最后一位默认为 0
        for (int i = 0; i < n; i++) {
            newHeights[i] = heights[i];
        }
        
        // 2. 单调栈 (存下标)
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
 
        for (int i = 0; i < newHeights.length; i++) {
            // 当当前高度 < 栈顶高度时，说明找到了栈顶元素的“右边界”
            // 必须是 while，因为当前元素可能比栈里好几个元素都矮
            while (!stack.isEmpty() && newHeights[stack.peek()] > newHeights[i]) {
                // 1. 弹出栈顶，作为高 (H)
                int curHeight = newHeights[stack.pop()];
                
                // 2. 获取对应的宽 (W)
                // 右边界是 i (当前元素的下标)
                // 左边界是栈顶元素 (弹出 cur 后剩下的栈顶)
                int curWidth;
                if (stack.isEmpty()) {
                    curWidth = i; // 如果栈空了，说明 curHeight 是目前最矮的，一直延伸到 0
                } else {
                    curWidth = i - stack.peek() - 1; // 标准公式：右 - 左 - 1
                }
 
                // 3. 更新面积
                maxArea = Math.max(maxArea, curHeight * curWidth);
            }
            // 保持单调递增，入栈
            stack.push(i);
        }
 
        return maxArea;
    }
}