1. 问题背景与核心挑战柱状图最大矩形问题Largest Rectangle in Histogram是LeetCode上经典的Hard级别题目编号84。给定n个非负整数表示柱状图的高度每个柱子的宽度为1求该柱状图中能够勾勒出的最大矩形面积。例如对于高度数组[2,1,5,6,2,3]最大矩形面积为10对应高度5和6的两个柱子。这个问题的暴力解法时间复杂度为O(n²)而采用单调栈Monotonic Stack可以将复杂度优化到O(n)。但单调栈的实现细节中存在多个易错点如何处理柱状图左右边界何时进行出栈操作宽度计算时索引的加减关系空栈和遍历结束时的特殊处理2. 单调栈算法原理解析2.1 单调栈的核心思想单调栈是一种特殊的栈结构栈内元素保持单调递增或递减的顺序。在本问题中我们使用单调递增栈栈底到栈顶高度递增其工作原理是遍历每个柱子时如果当前高度小于栈顶高度则不断弹出栈顶元素并计算面积面积计算的三个关键要素高度被弹出柱子的高度左边界新栈顶元素的索引栈空时为-1右边界当前遍历的索引宽度 右边界 - 左边界 - 12.2 Java实现代码框架public int largestRectangleArea(int[] heights) { DequeInteger stack new ArrayDeque(); int maxArea 0; int n heights.length; for (int i 0; i n; i) { int h (i n) ? 0 : heights[i]; // 末尾添加高度0的哨兵 while (!stack.isEmpty() h heights[stack.peek()]) { int height heights[stack.pop()]; int width stack.isEmpty() ? i : i - stack.peek() - 1; maxArea Math.max(maxArea, height * width); } stack.push(i); } return maxArea; }2.3 关键点说明哨兵技巧在数组末尾添加高度为0的虚拟柱子确保所有真实柱子都能被处理索引存储栈中存储的是柱子的索引而非高度值方便宽度计算等值处理遇到相等高度时可以弹出也可以保留不影响最终结果3. 算法步骤的逐行解析3.1 初始化阶段DequeInteger stack new ArrayDeque(); int maxArea 0; int n heights.length;使用ArrayDeque比Stack类性能更好约快3倍maxArea初始化为0对应空柱状图的情况获取数组长度避免多次计算3.2 主循环逻辑for (int i 0; i n; i) { int h (i n) ? 0 : heights[i]; // ...处理逻辑... }循环条件i n是为了处理末尾的哨兵值三目运算符简洁处理边界条件3.3 出栈计算面积while (!stack.isEmpty() h heights[stack.peek()]) { int height heights[stack.pop()]; int width stack.isEmpty() ? i : i - stack.peek() - 1; maxArea Math.max(maxArea, height * width); }h heights[stack.peek()]触发出栈条件弹出栈顶后新栈顶元素就是左边界空栈时宽度直接取i左边界为-13.4 入栈操作stack.push(i);当前索引入栈保持栈的单调递增性注意这是在while循环之后执行4. 复杂度分析与优化证明4.1 时间复杂度每个元素最多入栈和出栈各一次虽然嵌套循环但内层while循环的总操作次数不超过2n因此时间复杂度严格为O(n)4.2 空间复杂度最坏情况下所有柱子依次递增栈空间为O(n)平均情况也接近O(n)4.3 算法正确性证明关键点在于当柱子i被弹出时它的左右边界已经确定右边界第一个比它矮的柱子当前i左边界栈中下一个元素比它矮的最近的柱子因此计算出的面积是该柱子能扩展的最大矩形5. 边界条件与测试用例设计5.1 典型测试用例// 常规情况 int[] case1 {2,1,5,6,2,3}; // 应返回10 // 全等高度 int[] case2 {4,4,4,4}; // 应返回16 // 单柱 int[] case3 {5}; // 应返回5 // 空数组 int[] case4 {}; // 应返回0 // 锯齿形 int[] case5 {1,3,2,1,2,1}; // 应返回65.2 特殊边界处理空输入直接返回0单元素返回该元素值全递增需要末尾哨兵触发计算全递减需要逐个弹出计算6. 单调栈的变种与应用6.1 相关LeetCode题目每日温度No.739找下一个更高温度的天数接雨水No.42计算凹陷区域的储水量最大矩形No.85二维矩阵中的最大全1矩形6.2 工程应用场景股票分析中的支撑/阻力位识别图像处理中的连通区域分析内存分配中的最佳适配算法7. 常见错误与调试技巧7.1 典型错误模式宽度计算错误错误i - stack.peek()正确i - stack.peek() - 1哨兵遗漏未处理末尾导致栈中残留元素解决方法添加高度0的虚拟柱子等值处理不当遇到相等高度时错误弹出实际上可以保留不影响结果7.2 Debug技巧打印栈状态System.out.println(Pop height, widthwidth [(stack.isEmpty()?-1:stack.peek())..i]);可视化跟踪索引: 0 1 2 3 4 5 6 高度: 2 1 5 6 2 3 0(哨兵)断点设置在while循环开始处设置条件断点监控stack和maxArea的变化8. 算法优化与扩展8.1 空间优化版本可以复用原数组作为栈但会破坏输入数据int top -1; int[] stack new int[heights.length 1]; for (int i 0; i heights.length; i) { int h (i heights.length) ? 0 : heights[i]; while (top 0 h heights[stack[top]]) { int height heights[stack[top--]]; int width (top -1) ? i : i - stack[top] - 1; maxArea Math.max(maxArea, height * width); } stack[top] i; }8.2 分治法解决方案虽然时间复杂度为O(nlogn)但作为思维拓展public int calculateArea(int[] heights, int start, int end) { if (start end) return 0; int minIndex start; for (int i start; i end; i) { if (heights[i] heights[minIndex]) minIndex i; } return Math.max(heights[minIndex] * (end - start 1), Math.max(calculateArea(heights, start, minIndex - 1), calculateArea(heights, minIndex 1, end))); }8.3 动态规划变种预处理左右边界数组int[] left new int[n]; int[] right new int[n]; // 填充left和right数组 for (int i 0; i n; i) { int p i - 1; while (p 0 heights[p] heights[i]) p left[p]; left[i] p; } // 类似处理right数组 // 然后计算maxArea9. 面试考察要点9.1 常见考察方向算法思路能否想到单调栈边界处理空栈、等值、哨兵复杂度分析证明O(n)时间代码实现索引处理是否准确9.2 回答策略先描述暴力解法再引出优化思路重点解释单调栈的运作机制强调哨兵技巧的重要性准备测试用例验证代码10. 实际编码建议代码风格使用Deque而非Stack类变量命名清晰如leftBound而非简单的left添加必要注释说明关键步骤防御性编程if (heights null) return 0; if (heights.length 0) return 0;性能考量预先计算数组长度使用基本类型而非包装类避免不必要的对象创建在解决这个问题时我发现很多面试者容易在宽度计算上出错。一个实用的技巧是在纸上画出柱状图手动模拟算法运行过程标注每次弹出时的左右边界。这样能直观理解i - stack.peek() - 1的含义——减1是因为柱子宽度为1两个相邻柱子的间距是0。