【Java算法】柱状图中最大矩形，单调栈入门必学！✨

在这里插入图片描述

前言

亲爱的同学们，大家好呀！👋 今天我要和大家分享一个超级经典又有趣的算法问题——柱状图中的最大矩形。这个问题不仅是算法面试的高频题，更是学习单调栈这一强大数据结构的绝佳案例！🌟

你是否曾经看到过这样一道题：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出的最大矩形的面积。乍一看，这个问题似乎很复杂，但当你掌握了单调栈的精髓后，解决起来竟然如此优雅！💡

今天，我将带领大家一步步揭开柱状图中最大矩形问题的神秘面纱，从问题分析到代码实现，再到算法优化，让你彻底掌握这个经典算法！准备好开启这段算法之旅了吗？Let’s go! 🚀

知识点说明

1. 什么是柱状图中的最大矩形问题？🤔

柱状图是由若干紧靠的矩形组成的图形，每个矩形代表一个柱子，其高度由给定的非负整数表示，宽度均为1。在这个柱状图中，我们需要找出能够勾勒出的最大矩形的面积。

例如，对于高度数组 [2,1,5,6,2,3]，最大矩形的面积是10（由高度为5和6的两个柱子组成，高度取5，宽度为2）。

2. 解决方案概述 🛠️

解决柱状图中最大矩形问题主要有以下几种方法：

1. 暴力法：对于每个柱子，向左右扩展，找到以当前柱子高度为高的最大矩形。时间复杂度为O(n²)。
2. 分治法：将问题分解为左半部分、右半部分和跨中间的三个子问题。时间复杂度为O(nlogn)。
3. 单调栈法：利用单调栈在O(n)时间内找到每个柱子左右两侧第一个比它矮的柱子。时间复杂度为O(n)。

今天我们主要讲解单调栈方法，因为它不仅高效，而且是解决此类问题的通用技巧。

3. 什么是单调栈？💭

单调栈是一种特殊的栈，在这个栈中的元素始终保持单调递增或单调递减的顺序。对于柱状图中最大矩形问题，我们通常使用单调递增栈。

单调栈的核心思想是：当我们遍历到一个新元素时，如果它破坏了栈的单调性，我们就不断弹出栈顶元素，直到栈重新满足单调性，然后将新元素入栈。

通过这种方式，我们可以在O(n)时间内找到每个元素左右两侧第一个比它小（或大）的元素，这正是解决柱状图中最大矩形问题的关键。

重难点说明

1. 理解单调栈的工作原理 🔍

单调栈的精髓在于：当我们遍历到一个新元素时，栈中保存的是所有还没有找到右边界的元素。

对于柱状图中最大矩形问题，我们使用单调递增栈，具体工作原理如下：

1. 遍历柱状图中的每个柱子。
2. 如果栈为空或当前柱子的高度大于等于栈顶柱子的高度，将当前柱子的索引入栈。
3. 如果当前柱子的高度小于栈顶柱子的高度，说明我们找到了栈顶柱子的右边界。此时，我们弹出栈顶元素，计算以该柱子为高度的最大矩形面积。
4. 重复步骤3，直到栈为空或当前柱子的高度大于等于栈顶柱子的高度。
5. 将当前柱子的索引入栈。
6. 遍历完所有柱子后，栈中可能还有元素。我们依次弹出栈中的元素，计算以每个柱子为高度的最大矩形面积。

2. 处理边界情况 ⚠️

在实现单调栈算法时，有两个重要的边界情况需要特别注意：

1. 左边界：如果栈为空，说明当前柱子左侧没有比它矮的柱子，左边界为-1。
2. 右边界：如果遍历完所有柱子后栈中还有元素，说明这些柱子右侧没有比它矮的柱子，右边界为n（柱子的总数）。

为了简化代码，我们可以在高度数组的两端添加高度为0的哨兵柱子，这样就不需要特别处理边界情况了。

3. 计算最大矩形面积 📊

对于每个柱子，一旦我们知道了它左右两侧第一个比它矮的柱子的位置，就可以计算以该柱子高度为高的最大矩形面积：

面积 = 高度 × 宽度 = heights[i] × (右边界 - 左边界 - 1)

其中，左边界是左侧第一个比当前柱子矮的柱子的索引，右边界是右侧第一个比当前柱子矮的柱子的索引。

核心代码说明

下面我们来看看柱状图中最大矩形问题的Java实现代码：

方法一：使用单调栈（不添加哨兵）

public class LargestRectangleInHistogram {
    
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int n = heights.length;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i <= n; i++) {
            // 当遍历到数组末尾或当前高度小于栈顶索引对应的高度时
            int h = (i == n) ? 0 : heights[i];
            
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                // 弹出栈顶元素，计算以该柱子为高度的最大矩形面积
                int height = heights[stack.pop()];
                // 计算宽度：右边界(i) - 左边界(栈顶元素或-1) - 1
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                // 更新最大面积
                maxArea = Math.max(maxArea, height * width);
            }
            
            stack.push(i);
        }
        
        return maxArea;
    }
}

方法二：使用单调栈（添加哨兵）

public class LargestRectangleInHistogram {
    
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        int n = heights.length;
        // 添加哨兵，简化边界处理
        int[] newHeights = new int[n + 2];
        System.arraycopy(heights, 0, newHeights, 1, n);
        // 左右两端添加高度为0的哨兵
        newHeights[0] = 0;
        newHeights[n + 1] = 0;
        
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // 先把左哨兵入栈
        
        for (int i = 1; i < n + 2; i++) {
            while (newHeights[i] < newHeights[stack.peek()]) {
                int height = newHeights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        
        return maxArea;
    }
}

代码执行过程可视化 🎬

让我们通过一个例子来可视化单调栈的执行过程。假设输入高度数组为 [2, 1, 5, 6, 2, 3]：

1. 初始状态：stack = []
2. i=0, heights[0]=2：
   • 栈为空，直接入栈
   • stack = [0]
3. i=1, heights[1]=1：
   • 1 < heights[0]=2，弹出栈顶元素0
   • 计算面积：heights[0] * (1 - (-1) - 1) = 2 * 1 = 2
   • 栈为空，入栈1
   • stack = [1]
4. i=2, heights[2]=5：
   • 5 > heights[1]=1，直接入栈
   • stack = [1, 2]
5. i=3, heights[3]=6：
   • 6 > heights[2]=5，直接入栈
   • stack = [1, 2, 3]
6. i=4, heights[4]=2：
   • 2 < heights[3]=6，弹出栈顶元素3
   • 计算面积：heights[3] * (4 - 2 - 1) = 6 * 1 = 6
   • 2 < heights[2]=5，弹出栈顶元素2
   • 计算面积：heights[2] * (4 - 1 - 1) = 5 * 2 = 10
   • 2 > heights[1]=1，入栈4
   • stack = [1, 4]
7. i=5, heights[5]=3：
   • 3 > heights[4]=2，直接入栈
   • stack = [1, 4, 5]
8. i=6（数组末尾）：
   • 弹出所有栈中元素，计算面积
   • 弹出5，计算面积：heights[5] * (6 - 4 - 1) = 3 * 1 = 3
   • 弹出4，计算面积：heights[4] * (6 - 1 - 1) = 2 * 4 = 8
   • 弹出1，计算面积：heights[1] * (6 - (-1) - 1) = 1 * 6 = 6

最大面积为10，对应的是以索引2（高度为5）为高度的矩形，宽度为2（索引2和3）。

对Java初期学习的重要意义

1. 培养算法思维 🧠

柱状图中最大矩形问题是单调栈的经典应用，通过学习这个问题，你可以培养解决复杂问题的能力。单调栈是一种强大的数据结构，掌握它将帮助你解决更多高级算法问题。

2. 理解栈的高级应用 📚

栈是一种基本的数据结构，但单调栈展示了栈在解决特定问题时的强大威力。通过学习单调栈，你可以深入理解栈的高级应用，拓展你的数据结构知识。

3. 提升编程实现能力 💻

实现单调栈算法需要熟练运用栈操作、循环、条件判断等基本编程技能。通过编写这些代码，你可以提升自己的编程实现能力。

4. 学习问题抽象与建模 🔄

将实际问题抽象为柱状图中最大矩形问题是一种重要的思维训练。在软件开发中，我们经常需要将复杂的业务问题抽象为可计算的模型。

5. 为高级算法打基础 🏗️

单调栈是解决许多高级算法问题的基础，如接雨水、下一个更大元素等。掌握单调栈后，你可以更容易地理解和学习这些高级算法。

总结

亲爱的同学们，今天我们一起学习了柱状图中最大矩形这个经典算法问题。💯

我们了解了什么是柱状图中的最大矩形问题，以及解决这个问题的最优方法——单调栈。单调栈通过维护一个单调递增的栈，能够在O(n)时间内找到每个柱子左右两侧第一个比它矮的柱子，从而计算出以每个柱子为高度的最大矩形面积。

我们还详细讲解了单调栈的工作原理、边界情况的处理以及如何计算最大矩形面积。通过可视化的例子，我们一步步展示了单调栈的执行过程，帮助大家更直观地理解这个算法。

柱状图中最大矩形问题虽然看起来复杂，但通过单调栈这一巧妙的数据结构，我们可以优雅高效地解决它。这种思想不仅适用于这个问题，还可以应用到许多其他算法问题中。🏆

记住，算法学习不是一蹴而就的，需要不断的练习和思考。希望你能将今天学到的单调栈知识应用到更多的问题中，不断提升自己的算法能力。

如果你对柱状图中最大矩形问题或单调栈还有任何疑问，欢迎在评论区留言讨论。学习是一个持续的过程，让我们一起在算法的世界中探索和成长吧！✨

记得点赞、收藏、分享哦！下期我们将继续探讨更多有趣的算法知识，敬请期待！👋

#Java学习 #算法基础 #单调栈 #柱状图最大矩形 #编程教学