单调栈详解

一、引言

单调栈是一种特殊的栈结构，它在栈的基础上增加了单调性约束，即栈内的元素必须保持单调递增或单调递减的顺序。这种数据结构在解决某些特定问题时非常高效，例如求解下一个更大/更小元素、计算柱状图中的最大矩形面积等。本文将详细介绍单调栈的原理、实现以及应用场景。

二、单调栈的基本原理

1、单调栈的定义

单调栈是一种特殊的栈，栈内的元素必须保持单调递增或单调递减的顺序。根据栈的单调性，单调栈可以分为单调递增栈和单调递减栈：

• 单调递增栈：从栈底到栈顶，元素单调递增。
• 单调递减栈：从栈底到栈顶，元素单调递减。

2、单调栈的维护

单调栈的核心在于维护其单调性。当新元素入栈时，需要根据栈的单调性决定是否弹出栈顶元素。例如：

• 对于单调递增栈，如果新元素大于栈顶元素，则直接入栈；否则，弹出栈顶元素，直到满足单调性。
• 对于单调递减栈，逻辑相反。

三、单调栈的应用场景

单调栈主要用于解决以下两类问题：

1. 求解下一个更大/更小元素：通过单调栈，可以在一次遍历中找到每个元素的下一个更大或更小元素。
2. 计算柱状图中的最大矩形面积：利用单调栈可以高效地找到每个柱子的左右边界，从而计算最大矩形面积。

四、使用示例

1、求解下一个更大元素

以下是使用单调栈求解数组中每个元素的下一个更大元素的代码示例：

java复制

public int[] nextGreaterElement(int[] nums) {int[] result = new int[nums.length];Arrays.fill(result, -1); // 初始化结果数组Deque<Integer> stack = new ArrayDeque<>(); // 使用单调栈for (int i = 0; i < nums.length; i++) {// 如果栈不为空且当前元素大于栈顶元素while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {int index = stack.pop(); // 弹出栈顶元素result[index] = nums[i]; // 更新结果数组}stack.push(i); // 当前索引入栈}return result;
}

2、计算柱状图中的最大矩形面积

以下是使用单调栈计算柱状图中最大矩形面积的代码示例：

java复制

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

五、总结

单调栈是一种高效的数据结构，适用于解决特定的算法问题。通过维护栈的单调性，单调栈可以在一次遍历中完成复杂的计算，时间复杂度为O(n)。然而，单调栈的适用范围有限，仅适用于特定类型的问题。在实际应用中，我们需要根据问题的特点选择合适的数据结构和算法。

---

版权声明：本博客内容为原创，转载请保留原文链接及作者信息。

参考文章：

• 深入理解单调栈算法，这一篇就够了 - CSDN博客
• 《代码随想录》单调栈：高性能Java实现与详细图解 - CSDN博客