当前位置：首页 > news >正文

单调栈算法精解（Java实现）：从原理到高频面试题

news 2025/5/9 7:10:26

在算法与数据结构的领域中，单调栈（Monotonic Stack）凭借其独特的设计和高效的求解能力，成为解决特定类型问题的神兵利器。它通过维护栈内元素的单调性，能将许多问题的时间复杂度从暴力解法的\(O(n²)\)优化至\(O(n)\)，极大提升算法效率。本文将深入解析单调栈的核心思想、Java 实现方式，并结合 LeetCode 高频面试题，帮助读者透彻掌握这一重要算法工具。

一、单调栈核心思想

单调栈是一种特殊的数据结构，其核心在于保持栈内元素的单调性，这一特性使其在解决 “寻找下一个更大 / 更小元素” 类问题时表现卓越。它具有以下核心特性：

元素单调性：栈内元素始终保持严格递增或递减顺序，根据具体问题需求构建单调递增栈或单调递减栈。
后进先出机制：新元素入栈时，需与栈顶元素进行比较，根据单调性规则决定是否触发栈顶元素出栈。
时空效率优势：通过一次遍历完成操作，时间复杂度为\(O(n)\)；空间复杂度为\(O(n)\)，用于存储栈内元素。

二、单调栈两种形式

根据元素单调性的不同，单调栈可分为单调递增栈和单调递减栈，二者在操作规则与应用场景上各有侧重：

类型	操作规则	典型应用场景	适用问题特征
单调递增栈	新元素大于或等于栈顶元素时，栈顶元素出栈，直至满足单调性	寻找下一个更小元素、计算元素左侧 / 右侧第一个小于自身的元素	涉及局部最小值判断、区间边界查找的问题
单调递减栈	新元素小于或等于栈顶元素时，栈顶元素出栈，直至满足单调性	寻找下一个更大元素、计算元素左侧 / 右侧第一个大于自身的元素	涉及局部最大值判断、区间范围统计的问题

三、Java 实现模板

public class MonotonicStack {// 单调递减栈模板，用于寻找下一个更大元素public int[] nextGreaterElement(int[] nums) {int[] res = new int[nums.length];Arrays.fill(res, -1);Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < nums.length; i++) {while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {int idx = stack.pop();res[idx] = nums[i];}stack.push(i);}return res;}
}

上述代码展示了使用 Java 实现单调递减栈的核心逻辑：

通过Deque接口创建栈，ArrayDeque作为具体实现类，提供高效的栈操作。
遍历数组过程中，当新元素大于栈顶元素时，弹出栈顶元素并记录其下一个更大元素，最终栈内剩余元素的下一个更大元素为 -1。

四、经典问题解析

4.1 下一个更大元素 I（LeetCode 496）

题目要求：给定两个没有重复元素的数组 nums1 和 nums2 ，其中 nums1 是 nums2 的子集。返回 nums1 中每个元素在 nums2 中的下一个比其大的值。如果不存在，对应位置输出 -1。

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map<Integer, Integer> nextGreater = new HashMap<>();Deque<Integer> stack = new ArrayDeque<>();for (int num : nums2) {while (!stack.isEmpty() && num > stack.peek()) {nextGreater.put(stack.pop(), num);}stack.push(num);}int[] res = new int[nums1.length];for (int i = 0; i < nums1.length; i++) {res[i] = nextGreater.getOrDefault(nums1[i], -1);}return res;}
}

解题思路：

遍历 nums2 构建单调递减栈，同时使用哈希表记录每个元素的下一个更大元素。
遍历 nums1 ，通过哈希表快速获取对应元素的下一个更大元素，若不存在则返回 -1。

4.2 每日温度（LeetCode 739）

题目要求：给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < temperatures.length; i++) {while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {int idx = stack.pop();res[idx] = i - idx;}stack.push(i);}return res;}
}

解题思路：

利用单调递减栈存储温度的索引，当遇到更高温度时，计算当前温度与栈顶温度索引的差值，即为下一个更高温度的天数。

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

题目要求：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution {public int largestRectangleArea(int[] heights) {Deque<Integer> stack = new ArrayDeque<>();int maxArea = 0;int[] newHeights = Arrays.copyOf(heights, heights.length + 1);for (int i = 0; i < newHeights.length; i++) {while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {int h = newHeights[stack.pop()];int w = stack.isEmpty() ? i : i - stack.peek() - 1;maxArea = Math.max(maxArea, h * w);}stack.push(i);}return maxArea;}
}

解题思路：

在原始高度数组末尾添加一个 0，作为哨兵节点，确保所有元素都能被处理。
利用单调递增栈，计算每个高度对应的矩形宽度，从而得出最大矩形面积。

五、算法核心技巧

5.1 处理循环数组

// 循环数组解法（LeetCode 503）
public int[] nextGreaterElements(int[] nums) {int n = nums.length;int[] res = new int[n];Arrays.fill(res, -1);Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < 2 * n; i++) {int num = nums[i % n];while (!stack.isEmpty() && num > nums[stack.peek()]) {res[stack.pop()] = num;}if (i < n) stack.push(i);}return res;
}

技巧：通过将循环数组视为两倍长度的数组进行遍历，模拟循环效果，解决循环数组中寻找下一个更大元素的问题。

5.2 二维矩阵问题

// 最大矩形（LeetCode 85）
public int maximalRectangle(char[][] matrix) {if (matrix.length == 0) return 0;int[] heights = new int[matrix[0].length];int maxArea = 0;for (char[] row : matrix) {for (int j = 0; j < row.length; j++) {heights[j] = row[j] == '1' ? heights[j] + 1 : 0;}maxArea = Math.max(maxArea, largestRectangleArea(heights));}return maxArea;
}

技巧：将二维矩阵逐行转化为柱状图，通过复用柱状图中最大矩形的求解方法，解决二维矩阵中的最大矩形问题。

六、复杂度分析

问题类型	时间复杂度	空间复杂度	核心操作说明
一维数组	\(O(n)\)	\(O(n)\)	对数组进行单次遍历，栈操作复杂度与遍历次数相关
二维矩阵	\(O(mn)\)	\(O(n)\)	逐行处理矩阵，每行调用一维数组解法，m 为行数，n 为列数
循环数组	\(O(n)\)	\(O(n)\)	虚拟扩展数组长度为两倍，本质仍为单次遍历操作

七、常见错误与调试技巧

7.1 常见错误：

索引混淆：在栈中存储元素值还是元素索引不明确，导致后续计算错误。
边界处理：未正确处理栈为空的情况，或在数组边界处的操作逻辑错误。
相等处理：未明确元素相等时的出栈逻辑，影响单调性维护。
循环条件：遍历数组或处理栈操作时，循环方向判断错误，导致结果偏差。

7.2 调试方法：

打印栈状态：在关键操作处添加打印语句，跟踪栈内元素变化，定位逻辑错误。
小测试用例：使用简单、边界情况的测试用例，逐步验证算法正确性。
可视化辅助：通过画图、表格等方式，直观呈现栈的变化过程，辅助理解和调试。
暴力对比：将单调栈解法与暴力解法的结果进行对比，验证算法的准确性。

八、高频面试题扩展

接雨水（LeetCode 42）：利用单调栈计算柱状图中能接住的雨水量。
子数组最小值之和（LeetCode 907）：通过单调栈统计所有子数组中最小值的总和。
滑动窗口最大值（LeetCode 239）：结合单调队列（单调栈的扩展应用）实现高效求解。
移掉 K 位数字（LeetCode 402）：使用单调栈构造最小数字。
132 模式（LeetCode 456）：通过单调栈判断数组中是否存在 132 模式的子序列。

// 接雨水解法示例
class Solution {public int trap(int[] height) {Deque<Integer> stack = new ArrayDeque<>();int total = 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];total += w * h;}stack.push(i);}return total;}
}