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

Java 之「单调栈」：从入门到实战

article 2025/3/25 12:42:42

Java 单调栈：从入门到实战

文章目录

Java 单调栈：从入门到实战
- 引言
- 什么是单调栈？
- - 单调递增栈
  - 单调递减栈
- 单调栈的应用场景
- Java 实现单调栈
- - 代码示例：下一个更大元素
  - - 代码解析
- 单调栈的优势
- 实战应用：股票价格跨度
- - 代码示例
  - - 代码解析
- 总结
- - 参考资料

引言

在 Java 编程中，数据结构的选择和使用往往是解决复杂问题的关键。单调栈（Monotonic Stack）作为一种高效的数据结构，能够在 O(n) 时间复杂度内解决许多与单调性相关的问题，例如“下一个更大元素”、“股票价格跨度”等。对于 CSDN 的读者来说，深入理解单调栈不仅能提升代码能力，还能在面试和项目中脱颖而出。本文将带你从单调栈的基本概念入手，逐步深入到 Java 实现与实战应用，附上详细代码示例，让你轻松掌握这一利器！

什么是单调栈？

单调栈是一种特殊的栈结构，其核心在于保持栈内元素的单调性，即从栈底到栈顶元素要么单调递增，要么单调递减。在操作时，单调栈会通过弹出不符合单调性的元素来维持这一特性，从而在处理实时单调性问题时表现出色。

单调递增栈

定义：栈内元素从栈底到栈顶单调递增。
入栈规则：当新元素入栈时，如果栈顶元素大于或等于新元素，则不断弹出栈顶元素，直到栈顶小于新元素或栈为空。

单调递减栈

定义：栈内元素从栈底到栈顶单调递减。
入栈规则：当新元素入栈时，如果栈顶元素小于或等于新元素，则不断弹出栈顶元素，直到栈顶大于新元素或栈为空。

单调栈的这种动态调整机制，使其在特定场景下非常高效。

单调栈的应用场景

单调栈在算法和实际项目中有广泛应用，以下是几个经典场景：

下一个更大元素（Next Greater Element）：在数组中为每个元素找到右边第一个比它大的元素。
股票价格跨度（Stock Span Problem）：计算连续天数中股票价格不高于当天的最大天数。
直方图中最大矩形（Largest Rectangle in Histogram）：在直方图中找到面积最大的矩形。
温度预测：在温度数组中找到每个温度下一次更高温度出现的日子。

这些问题有一个共同点：需要快速找到某种单调关系，而单调栈正是解决这类问题的“杀手锏”。

Java 实现单调栈

在 Java 中，我们可以利用 java.util.Stack 类来实现单调栈。下面以“下一个更大元素”问题为例，展示单调递减栈的实现。

代码示例：下一个更大元素

import java.util.Stack;

public class MonotonicStackExample {
    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();
            }
            // 如果栈不为空，栈顶即为下一个更大元素，否则为 -1
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            // 当前元素入栈
            stack.push(nums[i]);
        }
        return result;
    }

    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 + " "); // 输出: 4 2 4 -1 -1
        }
    }
}

代码解析

栈的单调性：栈内元素保持单调递减。
遍历方向：从右向左遍历，便于找到右侧的更大元素。
逻辑：
1. 对于当前元素 nums[i]，弹出栈内所有小于等于它的元素。
2. 若栈为空，则右侧无更大元素，记为 -1；否则栈顶即为答案。
3. 将当前元素压入栈，继续处理下一个元素。

单调栈的优势

时间复杂度：每个元素最多入栈和出栈一次，总时间复杂度为 O(n)。
空间复杂度：最坏情况下栈存储所有元素，空间复杂度为 O(n)。
实时性：单调栈适合动态数据流场景，能实时维护单调性。

实战应用：股票价格跨度

问题描述：给定一个股票价格数组，计算每一天股票价格不高于当天的连续天数（包括当天）。

解法：使用单调递增栈，栈内存储价格及其对应的跨度，动态累加跨度。

代码示例

import java.util.Stack;

public class StockSpan {
    public static int[] stockSpan(int[] prices) {
        int n = prices.length;
        int[] spans = new int[n];
        Stack<int[]> stack = new Stack<>(); // 存储 [价格, 跨度]

        for (int i = 0; i < n; i++) {
            int span = 1;
            // 弹出栈内小于等于当前价格的元素，累加其跨度
            while (!stack.isEmpty() && stack.peek()[0] <= prices[i]) {
                span += stack.pop()[1];
            }
            spans[i] = span;
            stack.push(new int[]{prices[i], span});
        }
        return spans;
    }

    public static void main(String[] args) {
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        int[] spans = stockSpan(prices);
        for (int span : spans) {
            System.out.print(span + " "); // 输出: 1 1 1 2 1 4 6
        }
    }
}