力扣第84题-柱状图中最大矩形

题目
链接

题解

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        // 首尾带哨兵的数组
        int[] arrWithStl = new int[len + 2];
        System.arraycopy(heights, 0, arrWithStl, 1, len);
        len += 2;
        int res = 0;
        // 单调栈，存储下标
        Deque<Integer> stack = new ArrayDeque<>(len);
        // 哨兵入栈
        stack.addLast(0);
        // 遍历数组
        for (int i = 1; i < len; i++) {
            // 如果当前元素严格小于栈顶元素，弹栈并计算其构造的矩形面积
            while (arrWithStl[i] < arrWithStl[stack.peekLast()]) {
                // 高度就是数组存储的值
                int h = arrWithStl[stack.removeLast()];
                // 宽度是当前下标减去栈顶元素下标再减一
                // 因为栈顶元素一定在当前元素的左边，而且一定能扩散到当前元素的左边一个单位
                int w = i - stack.peekLast() - 1;
                // 计算答案
                res = Math.max(h * w, res);
            }
            // 当前元素下标压栈
            stack.addLast(i);
        }
        return res;
    }
}