Java怎么运用单调栈

Java怎么运用单调栈

单调栈（Monotonic Stack）是一种特殊的栈结构，它在处理一些特定问题时非常高效。单调栈的核心思想是维护一个栈，使得栈中的元素始终保持单调递增或单调递减的顺序。这种数据结构在解决一些与区间、边界、极值相关的问题时非常有用，比如寻找下一个更大元素、计算最大矩形面积等。

本文将详细介绍单调栈的概念、实现方式以及在Java中的具体应用，并通过几个经典问题来展示单调栈的强大之处。

---

1. 单调栈的基本概念

单调栈是一种栈结构，栈中的元素始终保持单调递增或单调递减的顺序。根据栈中元素的单调性，单调栈可以分为两种类型：

1. 单调递增栈：栈中的元素从栈底到栈顶是递增的。
2. 单调递减栈：栈中的元素从栈底到栈顶是递减的。

单调栈的核心思想是通过维护栈的单调性，快速找到某个元素的前驱或后继关系。例如，在寻找数组中每个元素的下一个更大元素时，单调栈可以高效地完成这一任务。

---

2. 单调栈的实现

在Java中，单调栈的实现通常基于Stack类或Deque接口。以下是单调栈的基本实现框架：

import java.util.Stack; public class MonotonicStack { public static void main(String[] args) { int[] nums = {2, 1, 2, 4, 3}; int[] result = nextGreaterElement(nums); for (int num : result) { System.out.print(num + " "); } } // 单调栈示例：寻找下一个更大元素 public static int[] nextGreaterElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); // 从后往前遍历数组 for (int i = n - 1; i >= 0; i--) { // 维护单调递减栈 while (!stack.isEmpty() && stack.peek() <= nums[i]) { stack.pop(); } // 如果栈不为空，当前元素的下一个更大元素是栈顶元素 result[i] = stack.isEmpty() ? -1 : stack.peek(); // 将当前元素压入栈中 stack.push(nums[i]); } return result; } } 

在上面的代码中，我们使用单调递减栈来寻找数组中每个元素的下一个更大元素。具体步骤如下：

1. 从后往前遍历数组。
2. 维护一个单调递减栈，如果栈顶元素小于等于当前元素，则弹出栈顶元素。
3. 如果栈不为空，当前元素的下一个更大元素就是栈顶元素；否则，当前元素没有下一个更大元素。
4. 将当前元素压入栈中。

---

3. 单调栈的应用场景

单调栈在解决一些与区间、边界、极值相关的问题时非常高效。以下是几个经典的应用场景：

3.1 寻找下一个更大元素

问题描述：给定一个数组，找到每个元素的下一个更大元素。如果不存在，则输出-1。

示例：

输入: [2, 1, 2, 4, 3] 输出: [4, 2, 4, -1, -1] 

Java实现：

public int[] nextGreaterElement(int[] nums) { int n = nums.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && stack.peek() <= nums[i]) { stack.pop(); } result[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(nums[i]); } return result; } 

3.2 计算最大矩形面积

问题描述：给定一个由非负整数组成的柱状图，计算其中可以勾勒出的最大矩形的面积。

示例：

输入: [2, 1, 5, 6, 2, 3] 输出: 10 

Java实现：

public int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; // 记录每个柱子左边第一个小于它的柱子的下标 int[] right = new int[n]; // 记录每个柱子右边第一个小于它的柱子的下标 Stack<Integer> stack = new Stack<>(); // 计算每个柱子左边第一个小于它的柱子的下标 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++) { maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1)); } return maxArea; } 

3.3 每日温度

问题描述：给定一个温度数组，表示每天的温度，返回一个数组，表示需要等待多少天才能遇到更高的温度。如果不存在，则输出0。

示例：

输入: [73, 74, 75, 71, 69, 72, 76, 73] 输出: [1, 1, 4, 2, 1, 1, 0, 0] 

Java实现：

public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) { int prevIndex = stack.pop(); result[prevIndex] = i - prevIndex; } stack.push(i); } return result; } 

---

4. 单调栈的复杂度分析

单调栈的时间复杂度通常是O(n)，其中n是数组的长度。这是因为每个元素最多只会被压入和弹出栈一次。

空间复杂度为O(n)，因为需要使用一个栈来存储元素。

---

5. 总结

单调栈是一种非常高效的数据结构，特别适合处理与区间、边界、极值相关的问题。通过维护栈的单调性，单调栈可以快速找到某个元素的前驱或后继关系，从而解决一些复杂的问题。

在Java中，单调栈的实现通常基于Stack类或Deque接口。通过几个经典问题的示例，我们可以看到单调栈在解决实际问题时的强大之处。掌握单调栈的使用方法，可以大大提高我们解决算法问题的效率。

希望本文对你理解单调栈的概念和应用有所帮助！