跳到主要内容

单调栈与单调队列

问题​

单调栈和单调队列的原理和常见题目？

答案​

单调栈​

维护一个栈底到栈顶单调递增/递减的栈，用于求每个元素左/右边第一个更大/更小的元素。

下一个更大元素（LeetCode 496/503）​

单调递减栈（栈底到栈顶递减）
public 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[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

每日温度（LeetCode 739）​

单调栈求右边第一个更大值的距离
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    return result;
}

接雨水（LeetCode 42）—— 单调栈解法​

单调递减栈，遇到更高的柱子计算积水
public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int w = i - left - 1;
            int h = Math.min(height[left], height[i]) - height[bottom];
            water += w * h;
        }
        stack.push(i);
    }
    return water;
}

柱状图中最大的矩形（LeetCode 84）​

单调递增栈，求每个柱子能扩展的最大宽度
public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

单调队列 —— 滑动窗口最大值（LeetCode 239）​

单调递减双端队列
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();  // 存索引，保持对应值单调递减
    int[] result = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        // 移除超出窗口的元素
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        // 维护单调性：弹出比当前值小的
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

常见面试问题​

Q1: 单调栈和普通栈的区别？​

答案：

普通栈不限制元素大小关系；单调栈在入栈时维护单调性，遇到破坏单调性的元素时弹出并处理。本质是用栈来高效找到每个元素的左/右边界。

Q2: 什么时候用单调栈，什么时候用单调队列？​

答案：

数据结构适用场景典型题
单调栈求左/右边第一个更大/更小元素每日温度、接雨水、最大矩形
单调队列滑动窗口内的最值滑动窗口最大值

Q3: 单调栈的时间复杂度？​

答案：

O(n)O(n)。每个元素最多入栈一次、出栈一次，总操作 O(2n)=O(n)O(2n) = O(n)。

相关链接​