悬线法是什么

悬线法（**Suspended Line Method**）是一种**用于解决二维矩阵中最大子矩阵问题**的高效算法，尤其适用于以下类型的问题： --- ## ✅ 问题背景 给定一个由 `0` 和 `1` 构成的二维矩阵，要求找出**全为 `1` 的最大矩形**或**最大正方形**。 悬线法的核心思想是： > **从每一行出发，维护一个“悬线”高度（连续为1的列长度），并记录该高度下可以向左、右扩展的最大边界**。 --- ## ✅ 悬线法三要素 1. `height[i][j]`：以 `(i,j)` 为底边的矩形最大高度（即向上连续为 `1` 的行数） 2. `left[i][j]`：在第 `i` 行中，以 `(i,j)` 为底边的悬线可以向左延伸的最远边界 3. `right[i][j]`：在第 `i` 行中，以 `(i,j)` 为底边的悬线可以向右延伸的最远边界 --- ## ✅ 悬线法的实现步骤 ### 1. 初始化 height 数组 - 如果当前格子为 `1`，则： ```cpp height[i][j] = height[i-1][j] + 1; ``` - 否则： ```cpp height[i][j] = 0; ``` ### 2. 计算 left 数组 - 从左到右遍历每一行： ```cpp if (grid[i][j] == 1) { left[i][j] = max(left[i][j-1], left_boundary); } else { left[i][j] = 0; // 或者设置为当前列最左边界 } ``` ### 3. 计算 right 数组 - 从右到左遍历每一行： ```cpp if (grid[i][j] == 1) { right[i][j] = min(right[i][j+1], rightBoundary); } else { right[i][j] = m-1; // 或者设置为当前列最右边界 } ``` ### 4. 更新最大矩形面积 - 对于每个 `(i,j)`，计算宽度： ```cpp width = right[i][j] - left[i][j] + 1; area = width * height[i][j]; max_area = max(max_area, area); ``` --- ## ✅ 示例：最大全1矩形 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 2005; int n, m; int grid[MAXN][MAXN]; int height[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN]; int max_rect = 0; int main() { cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> grid[i][j]; for (int i = 0; i < n; ++i) { // 初始化 left 边界 int l = 0; for (int j = 0; j < m; ++j) { if (grid[i][j] == 1) { if (i > 0 && grid[i][j]) { height[i][j] = height[i-1][j] + 1; } else { height[i][j] = 1; } if (j > 0 && grid[i][j-1] == 1) { l = max(l, left[i][j-1]); } else { l = j; } } else { height[i][j] = 0; l = j; } left[i][j] = l; } // 初始化 right 边界 int r = m - 1; for (int j = m - 1; j >= 0; --j) { if (grid[i][j] == 1) { if (j < m - 1 && grid[i][j+1] == 1) { r = min(r, right[i][j+1]); } else { r = j; } } else { r = j; } right[i][j] = r; } // 更新最大矩形面积 for (int j = 0; j < m; ++j) { if (grid[i][j] == 1) { int w = right[i][j] - left[i][j] + 1; int h = height[i][j]; max_rect = max(max_rect, w * h); } } } cout << max_rect << endl; return 0; } ``` --- ## ✅ 优点 - 时间复杂度低：`O(n * m)` - 空间复杂度低：`O(n * m)` - 实现相对简单，适合竞赛场景 --- ## ✅ 适用场景 - 最大全1矩形/正方形 - 黑白棋盘最大子矩阵 - 直方图中最大矩形问题的二维扩展 --- ##