动态规划：找出所有以指定单元格为最大值的子矩阵

核心思路 #

不要直接枚举所有子矩阵（复杂度高达O(N²M²)，还会重复统计），而是针对每个元素，计算它能成为最大值的所有子矩阵的范围——每个子矩阵只会被它的唯一最大值元素统计一次，从根源避免重复。

具体实现步骤 #

1. 预处理每行的左右边界（O(NM)）

对矩阵的每一行i，用单调栈计算两个数组：

• left[i][j]：第i行中，j列左边第一个严格大于matrix[i][j]的元素的列索引（无则为-1）。
• right[i][j]：第i行中，j列右边第一个大于等于matrix[i][j]的元素的列索引（无则为矩阵列数M）。

注：用严格大于和大于等于的区别，是为了处理相同元素的场景，确保每个子矩阵的最大值唯一对应一个元素，彻底避免重复统计。

2. 固定上下边界，统计有效子矩阵（O(N²M)）

遍历所有可能的上边界top（从0到N-1）：

• 初始化min_left和max_right数组，初始值分别为left[top][j]和right[top][j]。
• 遍历下边界bottom（从top到N-1）：
  • 对每一列j，更新min_left[j] = max(min_left[j], left[bottom][j])——因为子矩阵覆盖top到bottom行，所以左右边界必须取所有行中left的最大值，确保整个子矩阵范围内j左边没有比matrix[bottom][j]大的元素。
  • 更新max_right[j] = min(max_right[j], right[bottom][j])——同理，右边边界取所有行中right的最小值，确保整个子矩阵范围内j右边没有大于等于matrix[bottom][j]的元素。
  • 此时，在top到bottom的行范围内，以matrix[bottom][j]为最大值的子矩阵，列范围是(min_left[j], max_right[j])。任意选择左边界L（min_left[j] < L ≤ j）和右边界R（j ≤ R < max_right[j]），结合top-bottom的行范围，就构成一个符合要求的子矩阵。
  • 若要列出所有子矩阵，直接枚举L、R的组合即可；若只需要统计数量，可直接计算(j - min_left[j]) * (max_right[j] - j)。

解决重复统计问题 #

你之前直接枚举所有子矩阵的方式，会导致同一个子矩阵被多个元素错误关联（比如子矩阵的最大值是元素A，但遍历到该子矩阵时可能会误算到元素B）。而本方法中，通过左右边界的严格/非严格规则，每个子矩阵只会被它的唯一最大值元素统计，完全避免重复。

示例验证（以你给出的3x3矩阵为例） #

1 2 3
4 5 6
7 8 9

以元素5（位置(1,1)，0-based）为例：

• 第1行的left[1][1] = 0（左边元素4<5，再左无更大元素），right[1][1] = 2（右边元素6>5）。
• 当top=0、bottom=1时：
  • min_left[1] = max(left[0][1]=-1, left[1][1]=0) = 0
  • max_right[1] = min(right[0][1]=2, right[1][1]=2) = 2
  • 列范围是(0,2)，枚举L和R：
    • L=1, R=1 → 子矩阵[[5]]
    • L=0, R=1 → 子矩阵[[1,2],[4,5]]
      完全匹配你示例中的结果。

再以元素3（位置(0,2)）为例：

• 第0行的left[0][2] = -1（左边无严格大于3的元素），right[0][2] = 3（无右边元素）。
• 当top=0、bottom=0时：
  • 列范围是(-1,3)，枚举L和R：
    • L=0, R=2 → 子矩阵[[1,2,3]]
    • L=1, R=2 → 子矩阵[[2,3]]
    • L=2, R=2 → 子矩阵[[3]]
      与你示例中的三个子矩阵完全一致。

复杂度分析 #

• 预处理左右边界：每行单调栈处理为O(M)，N行总耗时O(NM)。
• 固定上下边界的循环：top有N种选择，每个top对应N-top个bottom，每个bottom处理M列，总耗时O(N²M)。当N与M接近时，复杂度为O(N³)，满足要求。

内容的提问来源于stack exchange，提问作者Ragnok123