每日算法 — 使用java实现栈：单调栈与直方图最大矩形求解

栈（Stack）是一种后进先出（LIFO）的线性数据结构，其操作仅限于在栈顶进行插入（push）和删除（pop）。虽然栈的实现极为简单，但基于栈的扩展应用却非常丰富。本文将从零实现一个动态扩容栈，并重点讲解单调栈这一高级技巧——它能够在 O(n) 时间内解决一类”寻找下一个更大/更小元素”的经典问题，以及直方图中最大矩形这类高频面试题。

数据结构原理

栈支持两种核心操作：push（压栈）将元素放到栈顶，pop（弹栈）移除并返回栈顶元素。由于只操作栈顶，所有操作均为 O(1)。

单调栈是栈的进阶应用，其核心思想是维护栈内元素的单调性（递增或递减）。当新元素破坏单调性时，持续弹出栈顶元素并处理，从而在一次遍历中完成复杂的状态转移。

Java 实现

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

/**
 * 栈的完整实现与单调栈高级应用
 */
public class StackDemo {

    /**
     * 基于数组的动态扩容栈
     */
    static class ArrayStack {
        private int[] data;
        private int size;
        private static final int DEFAULT_CAPACITY = 10;

        public ArrayStack() {
            data = new int[DEFAULT_CAPACITY];
            size = 0;
        }

        /**
         * 压栈操作
         */
        public void push(int val) {
            ensureCapacity();
            data[size++] = val;
        }

        /**
         * 弹栈操作
         *
         * @return 栈顶元素
         */
        public int pop() {
            if (isEmpty()) {
                throw new RuntimeException("Stack is empty");
            }
            return data[--size];
        }

        /**
         * 查看栈顶元素但不移除
         */
        public int peek() {
            if (isEmpty()) {
                throw new RuntimeException("Stack is empty");
            }
            return data[size - 1];
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        private void ensureCapacity() {
            if (size == data.length) {
                data = Arrays.copyOf(data, data.length * 2); // 容量翻倍
            }
        }
    }

    /**
     * 单调栈应用一：寻找每个元素的下一个更大元素
     * 给定数组，返回每个元素右边第一个比它大的元素，不存在则为 -1
     *
     * @param nums 输入数组
     * @return 下一个更大元素数组
     */
    public static int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // 默认无更大元素
        Deque<Integer> stack = new ArrayDeque<>(); // 存放下标，保持栈内元素值递减

        for (int i = 0; i < n; i++) {
            // 当当前元素大于栈顶元素时，栈顶元素的下一个更大元素就是当前元素
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int idx = stack.pop();
                result[idx] = nums[i];
            }
            stack.push(i);
        }
        // 栈中剩余元素无下一个更大元素，保持 -1
        return result;
    }

    /**
     * 单调栈应用二：寻找每个元素的左边第一个更小元素的下标
     *
     * @param heights 输入数组
     * @return 左边第一个更小元素的下标数组
     */
    public static int[] leftSmallerIndex(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // 单调递增栈

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        return left;
    }

    /**
     * 单调栈应用三：直方图中最大的矩形
     * 给定 n 个非负整数表示柱状图高度，求能勾勒出的最大矩形面积
     *
     * 核心思路：对每个柱子，找左右两边第一个比它矮的柱子，
     * 则该柱子为高的最大矩形宽度即为两边界距离
     *
     * @param heights 柱状图高度数组
     * @return 最大矩形面积
     */
    public static int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];  // 左边第一个更小元素的下标
        int[] right = new int[n]; // 右边第一个更小元素的下标
        Deque<Integer> stack = new ArrayDeque<>();

        // 计算左边界
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // 计算右边界
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        // 计算最大面积
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = right[i] - left[i] - 1; // 有效宽度
            int area = heights[i] * width;
            maxArea = Math.max(maxArea, area);
        }

        return maxArea;
    }

    /**
     * 优化版：一次遍历计算最大矩形面积
     * 在数组末尾添加高度为 0 的哨兵，确保所有元素都会被弹出处理
     */
    public static int largestRectangleAreaOptimized(int[] heights) {
        int n = heights.length;
        int[] h = Arrays.copyOf(heights, n + 1);
        h[n] = 0; // 哨兵
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;

        for (int i = 0; i <= n; i++) {
            while (!stack.isEmpty() && h[stack.peek()] > h[i]) {
                int height = h[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        // 测试基础栈
        ArrayStack stack = new ArrayStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("栈顶元素: " + stack.peek());
        System.out.println("弹栈: " + stack.pop());
        System.out.println("当前大小: " + stack.size());

        // 测试下一个更大元素
        int[] nums = {2, 1, 2, 4, 3};
        System.out.println("原始数组: " + Arrays.toString(nums));
        System.out.println("下一个更大元素: " + Arrays.toString(nextGreaterElement(nums)));

        // 测试最大矩形
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println("柱状图高度: " + Arrays.toString(heights));
        System.out.println("最大矩形面积: " + largestRectangleArea(heights));
        System.out.println("优化版最大矩形面积: " + largestRectangleAreaOptimized(heights));
    }
}

复杂度分析

单调栈将原本需要 O(n²) 的暴力枚举优化到 O(n)，其本质是利用栈维护了”尚未找到答案的元素”，在遍历过程中动态消除已解决的子问题。

适用场景

单调栈适用于以下场景：寻找下一个更大/更小元素；直方图最大矩形；接雨水（双指针也可用）；股票跨度问题；以及需要维护元素单调性的滑动窗口问题。掌握单调栈思想，是进阶算法能力的标志之一。