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接口。通过几个经典问题的示例，我们可以看到单调栈在解决实际问题时的强大之处。掌握单调栈的使用方法，可以大大提高我们解决算法问题的效率。

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