Java实现单调栈：从基础到实践

简介

在算法和数据结构的世界里，单调栈是一种特殊的数据结构，它在处理一些需要维护单调性的问题时表现出色。本文将深入探讨如何使用Java实现单调栈，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一强大的数据结构。

单调栈基础概念
Java实现单调栈
- 单调递增栈实现
- 单调递减栈实现
单调栈使用方法
- 解决的问题类型
- 算法思路
常见实践
- 下一个更大元素问题
- 柱状图中最大矩形面积问题
最佳实践
- 性能优化
- 代码规范与可读性
小结
参考资料

单调栈基础概念

单调栈是一种栈数据结构，其特点是栈内元素保持单调递增或单调递减的顺序。在单调递增栈中，从栈底到栈顶元素是递增的；而在单调递减栈中，从栈底到栈顶元素是递减的。当新元素入栈时，会将破坏单调性的元素从栈中弹出，直到栈恢复单调性。

单调栈常用于解决一些需要找到下一个更大（或更小）元素的问题，它能够在 $O(n)$ 的时间复杂度内解决这类问题，相比暴力解法有显著的性能提升。

Java实现单调栈

单调递增栈实现

import java.util.Stack;

public class MonotonicIncreasingStack {
    public static void main(String[] args) {
        int[] nums = {2, 7, 4, 8, 1, 9};
        int[] result = new int[nums.length];

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

单调递减栈实现

import java.util.Stack;

public class MonotonicDecreasingStack {
    public static void main(String[] args) {
        int[] nums = {2, 7, 4, 8, 1, 9};
        int[] result = new int[nums.length];

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

单调栈使用方法

解决的问题类型

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

寻找数组中每个元素的下一个更大（或更小）元素。
计算柱状图中最大矩形面积。
处理一些需要维护单调性的区间问题。

算法思路

初始化一个空栈。
遍历数组中的每个元素。
当栈不为空且当前元素与栈顶元素不满足单调性时，弹出栈顶元素，并处理相关逻辑（如记录下一个更大或更小元素）。
将当前元素入栈。
遍历结束后，处理栈中剩余元素。

常见实践

下一个更大元素问题

给定一个整数数组，找到数组中每个元素的下一个更大元素。如果不存在，则返回 -1。

import java.util.Stack;

public class NextGreaterElement {
    public static int[] nextGreaterElement(int[] nums) {
        int[] result = new int[nums.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 4, 8, 1, 9};
        int[] result = nextGreaterElement(nums);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

柱状图中最大矩形面积问题

给定一个表示柱状图高度的数组，计算柱状图中能够组成的最大矩形面积。

import java.util.Stack;

public class LargestRectangleArea {
    public static int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        int i = 0;

        while (i < heights.length ||!stack.isEmpty()) {
            int height = i < heights.length? heights[i] : 0;
            if (stack.isEmpty() || height >= heights[stack.peek()]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int width = stack.isEmpty()? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, heights[top] * width);
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(heights));
    }
}

最佳实践

性能优化

避免不必要的操作：在单调栈的实现中，尽量减少重复的计算和判断。例如，在弹出栈顶元素时，确保相关操作只执行一次。
使用合适的数据结构：Java中的Stack类虽然常用，但在性能上可能不如Deque接口的实现类。可以考虑使用ArrayDeque来提高性能。

代码规范与可读性

注释清晰：为代码添加详细的注释，特别是在关键步骤和逻辑处，帮助其他开发者理解代码的意图。
函数命名合理：函数名应准确反映其功能，例如nextGreaterElement、largestRectangleArea等。
模块化设计：将复杂的逻辑拆分成多个小函数，提高代码的可维护性和复用性。

小结

单调栈是一种强大的数据结构，能够高效地解决许多与单调性相关的问题。通过本文的介绍，读者应该对单调栈的基础概念、Java实现方法、使用场景以及最佳实践有了深入的了解。在实际应用中，灵活运用单调栈可以显著提升算法的性能和效率。

参考资料

《算法导论》
LeetCode官方文档
GeeksforGeeks相关文章