🌕 84. 柱状图中最大的矩形

难度: 🌕

问题描述

#

解法 单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 思路：
        // 借助栈 - 构造 严格递增栈
        // 添加虚拟节点，保证每个柱子的长度都会被计算到
        int len = heights.length;
        int[] array = new int[len + 2];
        System.arraycopy(heights, 0, array, 1, len);
        LinkedList<Integer> stack = new LinkedList<>();
        int res = 0;
        // 遍历
        len += 2;
        for(int i = 0; i < len; i ++) {
            if(stack.isEmpty()) {
                stack.push(i);
            } else {
                // stack 非空
                int cur = array[i];
                int tmpPeek = array[stack.peek()];
                if(cur > tmpPeek) {
                    stack.push(i);
                } else if(cur == tmpPeek) {
                    stack.pop();
                    stack.push(i); // 保证单调递增
                } else {
                    while(!stack.isEmpty() && cur <= array[stack.peek()]) {
                        int hi = array[stack.pop()];
                        // 弹出后判断是否为空
                        if(!stack.isEmpty()) {
                            int leftIndex = stack.peek();
                            int width = i - leftIndex - 1;
                            int square = hi * width;
                            res = Math.max(res, square);
                            // System.out.println(hi + "  " + i + "  " + leftIndex);
                        }
                    } 
                    stack.push(i);
                }
            }
        }
        return res;
    }
}

---

输出