JAVA:实现ILargestRectangle最大的矩形算法（附带源码）
1. 项目背景详细介绍
在很多工程与算法题中，都会遇到 “直方图中最大的矩形（Largest Rectangle in Histogram）” 问题：
给定一个非负整数数组 heights，其中 heights[i] 表示索引 i 处柱子的高度、宽度恒为 1。请返回能够在该直方图中形成的最大矩形面积。这是诸多问题的基础模块，例如：
-
图像处理/建筑规划：求最大连续可用高度范围；
-
数据可视化容错：找出一段区间的“支撑能力”极值；
-
二维“最大全 1 矩形（Maximal Rectangle）”问题的行扫描子问题；
-
股票/负载分析：在某些建模里可转化为柱状“支撑区”的最大面积估计。
经典示例：heights = [2,1,5,6,2,3] 的最大矩形面积是 10，对应于高度 5~6 的两根柱，宽度 2，面积 5*2=10（或 6*1+5*1 的组合区域）。
2. 项目需求详细介绍
-
输入：整型数组
int[] heights，heights.length可为0，元素为0+整数。 -
输出：最大矩形面积（为避免溢出，内部计算使用
long，最终返回long）。 -
接口：
public interface ILargestRectangle { long largestRectangleArea(int[] heights); } -
实现：至少给出一种 O(n) 的单调栈实现；可附加分治与暴力版本用于教学对比与校验。
-
健壮性：处理空数组、包含
0、全等高度、严格递增/递减等边界。 -
测试：提供
Main，包含多组样例与随机自测（对拍：O(n) 与 O(n^2) 结果一致性）。
3. 相关技术详细介绍
3.1 解法全景
-
暴力法 O(n²)：枚举每个起点/终点区间，或对每个
i向两侧扩展找最小高度。简单但慢。 -
分治法 O(n log n) ~ O(n²)：以最矮柱分割左右递归；若用线段树/稀疏表查最小值下标，可到 O(n log n)，否则最坏 O(n²)。
-
单调栈 O(n)（推荐）：维护单调递增高度下标栈；当遇到“破坏单调性”的更矮柱时，不断弹栈计算以被弹出柱为最低高度的最大面积。
3.2 单调栈要点
-
栈内存放的是索引，且对应的高度严格递增；
-
为便于收尾计算，常在数组首尾加哨兵 0；
-
当当前高度
h[i] < h[stack.peek()]：-
取出
top = stack.pop()，其高度H = h[top]为当前要结算的“最低柱”； -
right = i，left = stack.peek()（弹出后的新栈顶）； -
宽度
W = right - left - 1； -
面积
A = H * W，更新答案。
-
-
整体每根柱子最多进栈一次、出栈一次，总计 O(n)。
3.3 溢出与返回类型
若高度上限较大（比如可达 1e9），面积 = 高度 * 宽度 可能超过 int，故内部使用 long 计算并返回 long，更稳妥。
4. 实现思路详细介绍
-
接口化：
ILargestRectangle规范方法签名，方便替换不同实现； -
实现类：
-
LargestRectangleStack：单调栈 O(n)，生产环境首选； -
LargestRectangleDivideConquer：教学展示分治思路； -
LargestRectangleBruteForce：暴力法，用于对拍校验；
-
-
测试
Main：-
多组典型样例；
-
随机数组对拍：确保 O(n) 与 O(n²) 的答案一致；
-
覆盖边界：空数组、全 0、全等、单元素、递增、递减、含超大值。
-
5. 完整实现代码
import java.util.*;
/** ================= 接口定义 ================= */
interface ILargestRectangle {
/**
* @param heights 柱状图高度数组（允许为空或包含0）
* @return 直方图最大矩形面积（long，内部避免溢出）
*/
long largestRectangleArea(int[] heights);
}
/** =============== 实现一：单调栈 O(n)（推荐） =============== */
class LargestRectangleStack implements ILargestRectangle {
@Override
public long largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0L;
int n = heights.length;
// 新数组，首尾加“哨兵0”，简化边界
int[] h = new int[n + 2];
System.arraycopy(heights, 0, h, 1, n);
Deque<Integer> st = new ArrayDeque<>();
long ans = 0L;
for (int i = 0; i < h.length; i++) {
// 维持单调递增（栈顶对应高度 > 当前高度，则出栈结算）
while (!st.isEmpty() && h[st.peek()] > h[i]) {
int top = st.pop();
long height = h[top];
int right = i;
int left = st.peek(); // 弹出后新的栈顶
long width = right - left - 1;
long area = height * width;
if (area > ans) ans = area;
}
st.push(i);
}
return ans;
}
}
/** =============== 实现二：分治（最矮柱切分） =============== */
class LargestRectangleDivideConquer implements ILargestRectangle {
@Override
public long largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0L;
return solve(heights, 0, heights.length - 1);
}
private long solve(int[] h, int l, int r) {
if (l > r) return 0L;
if (l == r) return (long) h[l];
// 线性找最矮柱下标（可换成线段树以降复杂度）
int minIdx = l;
for (int i = l + 1; i <= r; i++) {
if (h[i] < h[minIdx]) minIdx = i;
}
long areaByMin = (long) h[minIdx] * (r - l + 1);
long left = solve(h, l, minIdx - 1);
long right = solve(h, minIdx + 1, r);
return Math.max(areaByMin, Math.max(left, right));
}
}
/** =============== 实现三：暴力 O(n^2)（教学/对拍） =============== */
class LargestRectangleBruteForce implements ILargestRectangle {
@Override
public long largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) return 0L;
int n = heights.length;
long ans = 0L;
for (int i = 0; i < n; i++) {
int minH = heights[i];
for (int j = i; j < n; j++) {
minH = Math.min(minH, heights[j]);
long area = (long) minH * (j - i + 1);
if (area > ans) ans = area;
}
}
return ans;
}
}
/** ==================== 工具：随机生成与断言 ==================== */
class ArraysUtil {
static int[] randomNonNegativeArray(int n, int maxH, Random rnd) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = rnd.nextInt(maxH + 1); // [0, maxH]
return a;
}
static String arrToString(int[] a) {
return a == null ? "null" : Arrays.toString(a);
}
}
/** ==================== 测试驱动 Main ==================== */
public class Main {
public static void main(String[] args) {
ILargestRectangle fast = new LargestRectangleStack(); // O(n)
ILargestRectangle divide = new LargestRectangleDivideConquer();// 教学
ILargestRectangle slow = new LargestRectangleBruteForce(); // 对拍
// --- 1) 基本样例 ---
runCase(fast, new int[]{2,1,5,6,2,3}, 10L);
runCase(fast, new int[]{2,4}, 4L);
runCase(fast, new int[]{1}, 1L);
runCase(fast, new int[]{}, 0L);
runCase(fast, new int[]{0,0,0}, 0L);
runCase(fast, new int[]{2,2,2,2}, 8L);
runCase(fast, new int[]{1,2,3,4,5}, 9L); // 3*3 或 4*2 或 5*1 中最大为 9（3 高 × 3 宽）
runCase(fast, new int[]{5,4,3,2,1}, 9L); // 3*3
// --- 2) 与暴力对拍若干随机样例（小规模，确保一致性） ---
Random rnd = new Random(20250823);
for (int t = 0; t < 30; t++) {
int n = 1 + rnd.nextInt(12); // 小规模，暴力可承受
int[] a = ArraysUtil.randomNonNegativeArray(n, 10, rnd);
long ansFast = fast.largestRectangleArea(a);
long ansSlow = slow.largestRectangleArea(a);
if (ansFast != ansSlow) {
System.out.println("对拍失败：");
System.out.println("heights = " + ArraysUtil.arrToString(a));
System.out.println("fast = " + ansFast + ", slow = " + ansSlow);
throw new AssertionError("单调栈答案与暴力不一致！");
}
}
System.out.println("随机对拍通过 ✅");
// --- 3) 分治与单调栈在一些样例上校验一致 ---
int[][] tests = {
{2,1,5,6,2,3},
{1,2,3,4,5,4,3,2,1},
{6,2,5,4,5,1,6},
{1,1,1,1,1},
{4,2,0,3,2,5},
};
for (int[] a : tests) {
long A = fast.largestRectangleArea(a);
long B = divide.largestRectangleArea(a);
if (A != B) {
System.out.println("分治与单调栈不一致：heights=" + Arrays.toString(a));
System.out.println("stack=" + A + ", divide=" + B);
throw new AssertionError("实现不一致");
}
}
System.out.println("分治与单调栈在样例上结果一致 ✅");
System.out.println("所有用例通过 🎉");
}
private static void runCase(ILargestRectangle solver, int[] heights, long expect) {
long got = solver.largestRectangleArea(heights);
System.out.printf(Locale.ROOT,
"heights=%s -> maxArea=%d (期望=%d)%s%n",
Arrays.toString(heights), got, expect, (got == expect ? " ✅" : " ❌"));
if (got != expect) throw new AssertionError("结果与期望不符");
}
}
6. 代码详细解读
6.1 接口与实现解耦
-
ILargestRectangle使调用方只依赖抽象，便于随时切换算法实现（例如在数据规模小的时候用暴力，对拍时用双实现互检，线上用 O(n)）。
6.2 单调栈实现（核心）
-
哨兵：在数组两端补 0，保证所有柱都会在某个时刻被“更矮”的元素触发结算（最后的 0 强迫清空栈）。
-
栈中存索引：栈底到栈顶对应高度单调递增。
-
结算逻辑：当遇到更矮高度
h[i]时，持续弹栈：-
被弹出
top的那根柱以其高度为“最低”，左右边界就是弹出后栈顶left与当前i = right，宽度为right - left - 1。
-
-
复杂度：每个索引入栈一次、出栈一次，故 O(n)。
6.3 分治实现
-
选择区间
[l,r]的最矮柱minIdx：最大矩形要么跨越整个区间、以h[minIdx]为高；要么完全在左区间；要么在右区间。 -
若用线段树支持 RMQ（最小值下标查询）可到 O(n log n)，此处为教学版本，最坏 O(n²)。
6.4 暴力实现
-
枚举
[i..j]子区间，维护最小高度minH并更新最大面积。 -
仅用于校验，不建议在大数据规模使用。
6.5 溢出安全
-
面积用
long计算与返回，避免int乘法溢出。 -
若业务端确需
int，可以在调用处做边界判断与转换。
7. 项目详细总结
-
最佳实践：单调栈 O(n) 是工业级首选，简单、快速、可靠。
-
教育价值：分治与暴力为单调栈提供了思维对照与对拍工具。
-
鲁棒性：代码对空数组、包含 0、严格单调、全等等场景均处理正确；测试中也对拍了随机样例，保证正确性。
8. 项目常见问题及解答
Q1：为什么要加哨兵 0？
为了统一结算逻辑，避免在遍历结束后还要单独清空栈；末尾的 0 一定会比栈内所有正高度更矮，从而触发所有剩余柱的结算。
Q2：栈里为什么存索引而不是高度？
需要通过索引获取左右边界：left 为弹栈后的新栈顶，right 为当前下标；若只存高度难以获知宽度。
Q3：能否在原数组上修改减少空间？
可以不复制数组、只在末尾追加一次结算（额外循环清栈），效果相同；本文用哨兵写法换来更清晰的主循环。
Q4：为什么返回 long？
当 heights[i] 很大时，高度 × 宽度 容易超出 int 范围，使用 long 更安全。
Q5：如何将该算法应用到“最大全 1 矩形（Maximal Rectangle）”？
对每一行把“连续 1 的高度”当作直方图高度，逐行调用本算法，取全局最大值即可。
9. 扩展方向与性能优化
-
RMQ/线段树分治：将“找最小值下标”降到 O(log n)，整体 O(n log n)。
-
并行优化：极端大数组可做分块并行计算候选，再合并边界（实现复杂，一般不必）。
-
内存友好：若对 GC 压力敏感，可重用栈与辅助数组，减少对象分配。
-
二维拓展：直接套用于“最大全 1 矩形”，作为行高直方图的核心子程序。
-
在线流式：若数据流入不断变化，可维护递增栈并在窗口滑动时增删元素（需要更复杂的数据结构与懒删除）。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
15
0- 0
已为社区贡献484条内容
所有评论(0)