2026-08-26：矩阵中的局部最大值Ⅱ。用go语言，给定一个大小为 n 行 m 列的整数矩阵，矩阵里所有数字都是大于等于 0 的。 对于矩阵中任意一个数值大于 0 的格子（称为“当前格子”），我们

2026-08-26：矩阵中的局部最大值Ⅱ。用go语言，给定一个大小为 n 行 m 列的整数矩阵，矩阵里所有数字都是大于等于 0 的。

对于矩阵中任意一个数值大于 0 的格子（称为“当前格子”），我们以它的数值作为半径，检查它周围的一个特定区域：

• 这个区域包括：以当前格子为中心，向上、下、左、右各延伸“当前数值”那么多行的所有格子。

• 但是，要排除那些行方向和列方向的距离都恰好等于当前数值的格子（也就是四个角上的最远点）。

• 同时，超出矩阵边界的格子不纳入考虑。

如果当前格子满足以下两个条件，就称它为“局部最大值”：

最后，你需要统计整个矩阵中这样的“局部最大值”一共有多少个，并返回这个数量。

1 <= n == matrix.length <= 200。

1 <= m == matrix[i].length <= 200。

0 <= matrix[i][j] <= 200。

输入： matrix = [[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,2,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]。

输出： 1。

解释：

对于非零单元格 (3, 3) ，x = matrix[3][3] = 2 。

高亮的单元格是在 (3, 3) 的 x 行和 x 列范围内被考虑的单元格。

行距离和列距离都等于 x = 2 的四个单元格被忽略。

没有一个被考虑的单元格的值大于 2 ，因此 (3, 3) 是一个局部最大值。

没有其他非零单元格，所以答案是 1 。

题目来自力扣3933。

第一步：问题核心逻辑理解

题目要求：

• 对于每个 > 0 的格子 (i, j)，其值为 x。
• 要检查一个以它为中心、半径 x 的方形区域（上下左右各延伸 x 行/列）。
• 但是，四个角的格子（即行差 == x 且 列差 == x 的位置）要排除在外。
• 如果该区域内没有比它更大的数，就计数为“局部最大值”。

这里“没有更大”的意思是可以有相等的值。

第二步：代码的整体结构

代码使用了 线段树 + 一维ST表 的二维范围最大值查询结构。

主要结构：

• 一维ST表（sparseTable）：可以快速查询一维数组任意区间的最大值。
• 线段树（seg）：每个节点维护的是一个一维ST表，这个ST表代表某段连续行在每一列上的最大值。

第三步：构建数据结构

1. 一维ST表

• 输入一个数组 a 和合并函数 op（这里是 max）。
• 构建 st 二维数组，st[k][j] 表示从 j 开始长度为 2^k 的区间的最大值。
• 查询 query(l, r) 时，利用 bits.Len8 快速得到区间长度对应的 k，然后合并两个重叠区间取最大值。
• 这里因为数据范围 ≤ 200，使用 bits.Len8 是安全的。

2. 线段树节点

• 线段树每个节点代表一个行区间 [l, r]。
• 叶子节点：直接对 matrix[l]（一行）建立一维ST表。
• 内部节点：
  • 先分别构建左右子树。
  • 取左右子树根节点（即对应行区间）的st[0]（长度为 m 的数组）逐列取最大值，形成新的长度为 m 的数组。
  • 再对这个新数组建立一维ST表。

这样，每个线段树节点就保存了该行区间内，每一列的最大值，并且支持快速查询任意列区间。

第四步：查询过程

对于每个格子 (i, j)，值 x：

• 我们要检查两个矩形区域的最大值：
• 区域A：行范围 [max(i-x, 0), min(i+x, n-1)]，列范围 [max(j-x+1, 0), min(j+x, m)]（注意列左边少1，右边含j+x，从而避开四个角中的左右角）。
• 区域B：行范围 [max(i-x+1, 0), min(i+x-1, n-1)]，列范围 [max(j-x, 0), min(j+x+1, m)]（行范围上下收缩一行，列范围扩展一格，也是避开四个角）。

这两个区域合起来正好就是去除四个角的完整方形区域（因为四个角在这两个区域里都被分别排除了）。

• 调用线段树的 query 方法，分别得到区域A和区域B的最大值。
• 如果这两个最大值都 ≤ x，则当前格子是局部最大值，计数加一。

第五步：线段树的 query 过程

query(node, l, r, r1, r2, c1, c2)：

• node：当前节点，管理行区间 [l, r]。
• [r1, r2]：要查询的行范围。
• [c1, c2)：要查询的列范围（左闭右开）。
• 如果当前节点完全被 [r1, r2] 包含，则直接返回该节点上ST表对列区间的查询结果。
• 否则，根据 [r1, r2] 与左右子树的交集，递归查询左右子树，并取最大值返回。

第六步：主流程

第七步：例子验证

给定全 0 矩阵，中间一个 2：

• 对于 (3,3)，x=2：
  • 区域A：行[1,5]，列[2,5]（排除左上角(1,1)和右上角(1,5)）
  • 区域B：行[2,4]，列[1,6]（排除左下角(5,1)和右下角(5,5)）
  • 这两个区域合起来就是除了四个角之外的整个 5×5 方形。
  • 全部为0，最大值0 ≤ 2，所以满足条件，计数为1。
• 其他格子值为0，不处理。
• 最终输出1。

时间与空间复杂度

时间复杂度

• 构建线段树：
  • 每个节点要构建一维ST表，ST表构建复杂度 O(m log m)。
  • 一共有 O(n) 个节点（线段树节点数约 4n），所以构建总复杂度 O(n * m log m)。
• 查询：
  • 每次查询需要 O(log n) 个线段树节点，每个节点做一次ST表查询 O(1)。
  • 每个格子最多做 2 次查询，格子总数 n*m。
  • 所以总查询复杂度 O(n*m * log n)。

总时间复杂度：O(n * m * (log m + log n))，在 n,m ≤ 200 时非常快。

额外空间复杂度

• 线段树每个节点存储一个ST表，每个ST表是二维数组，大小约 log m × m。
• 节点数 O(n)，所以总空间 O(n * m * log m)。
• 加上矩阵本身 O(n*m)。

总的额外空间复杂度：O(n * m * log m)。

Go完整代码如下：

package main

import (
"fmt"
"math/bits"
)

// 一维 ST 表（泛型版本）
type sparseTable[T any] struct {
st [][]T
op func(T, T) T
}

func newSparseTable[T any](a []T, op func(T, T) T) sparseTable[T] {
n := len(a)
w := bits.Len(uint(n))
st := make([][]T, w)
for i := range st {
st[i] = make([]T, n)
}
st[0] = a
for i := 1; i < w; i++ {
for j := range n – 1<<i + 1 {
st[i][j] = op(st[i–1][j], st[i–1][j+1<<(i–1)])
}
}
return sparseTable[T]{st, op}
}

func (s sparseTable[T]) query(l, r int) T {
k := bits.Len8(uint8(r–l)) – 1 // 本题数据范围小，可以用 Len8
return s.op(s.st[k][l], s.st[k][r–1<<k])
}

// 完整模板见 https://leetcode.cn/circle/discuss/mOr1u6/
type seg []sparseTable[int]

func (t seg) build(a [][]int, node, l, r int) {
if l == r { // 叶子
t[node] = newSparseTable(a[l], func(a, b int) int { return max(a, b) })
return
}

m := (l + r) / 2
t.build(a, node*2, l, m) // 初始化左子树
t.build(a, node*2+1, m+1, r) // 初始化右子树

merged := make([]int, len(a[0]))
for i := range merged {
merged[i] = max(t[node*2].st[0][i], t[node*2+1].st[0][i]) // 行号 [l, r] 中的第 i 列的最大值
}
t[node] = newSparseTable(merged, func(a, b int) int { return max(a, b) })
}

// 行号闭区间 [r1, r2]，列号左闭右开 [c1, c2)
func (t seg) query(node, l, r, r1, r2, c1, c2 int) int {
if r1 <= l && r <= r2 { // 当前子树完全在 [r1, r2] 内
return t[node].query(c1, c2)
}
m := (l + r) / 2
if r2 <= m { // [r1, r2] 在左子树
return t.query(node*2, l, m, r1, r2, c1, c2)
}
if r1 > m { // [r1, r2] 在右子树
return t.query(node*2+1, m+1, r, r1, r2, c1, c2)
}
return max(t.query(node*2, l, m, r1, r2, c1, c2), t.query(node*2+1, m+1, r, r1, r2, c1, c2))
}

func countLocalMaximums(matrix [][]int) (ans int) {
n, m := len(matrix), len(matrix[0])
// 线段树每个节点 [l, r] 保存的是，当上下边界固定为 l 和 r 时，把每一列的最大值视作一个 int，这 m 个数的一维 ST 表
t := make(seg, 2<<bits.Len(uint(n–1)))
t.build(matrix, 1, 0, n–1)

for i, row := range matrix {
for j, x := range row {
if x > 0 && max(t.query(1, 0, n–1, max(i–x, 0), min(i+x, n–1), max(j–x+1, 0), min(j+x, m)),
t.query(1, 0, n–1, max(i–x+1, 0), min(i+x–1, n–1), max(j–x, 0), min(j+x+1, m))) <= x {
ans++
}
}
}
return
}

func main() {
matrix := [][]int{{0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 2, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}}
result := countLocalMaximums(matrix)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from math import log2, ceil
from typing import List, Callable, TypeVar, Generic

T = TypeVar('T')

class SparseTable(Generic[T]):
"""一维ST表"""
def __init__(self, arr: List[T], op: Callable[[T, T], T]):
self.op = op
n = len(arr)
if n == 0:
self.st = []
return

# 计算log2
k = n.bit_length()
self.st = [[0] * n for _ in range(k)]
self.st[0] = arr[:] # 复制数组

for i in range(1, k):
step = 1 << (i – 1)
for j in range(n – (1 << i) + 1):
self.st[i][j] = op(self.st[i–1][j], self.st[i–1][j + step])

def query(self, l: int, r: int) –> T:
"""查询闭区间 [l, r] 的聚合结果"""
if l > r:
# 返回一个极小值，用于max操作
return float('-inf') if isinstance(self.op(0, 0), (int, float)) else None
length = r – l + 1
k = length.bit_length() – 1
return self.op(self.st[k][l], self.st[k][r – (1 << k) + 1])

class SegmentTree:
"""线段树，每个节点存储对应行区间的一维ST表"""
def __init__(self, matrix: List[List[int]]):
self.matrix = matrix
self.n = len(matrix)
self.m = len(matrix[0]) if matrix else 0

# 计算线段树大小
size = 1
while size < self.n:
size <<= 1
self.tree = [None] * (2 * size)
self.size = size

self._build(1, 0, self.n – 1)

def _build(self, node: int, l: int, r: int):
"""构建线段树"""
if l == r:
# 叶子节点：直接使用该行的ST表
self.tree[node] = SparseTable(self.matrix[l], max)
return

mid = (l + r) // 2
self._build(node * 2, l, mid)
self._build(node * 2 + 1, mid + 1, r)

# 合并左右子树：对每一列取最大值
merged = [
max(self.tree[node * 2].st[0][j], self.tree[node * 2 + 1].st[0][j])
for j in range(self.m)
]
self.tree[node] = SparseTable(merged, max)

def query(self, r1: int, r2: int, c1: int, c2: int) –> int:
"""
查询行区间 [r1, r2]，列区间 [c1, c2] 的最大值
"""
if r1 > r2 or c1 > c2:
return float('-inf')
return self._query(1, 0, self.n – 1, r1, r2, c1, c2)

def _query(self, node: int, l: int, r: int, r1: int, r2: int, c1: int, c2: int) –> int:
"""内部递归查询"""
if r1 <= l and r <= r2:
return self.tree[node].query(c1, c2)

mid = (l + r) // 2
if r2 <= mid:
return self._query(node * 2, l, mid, r1, r2, c1, c2)
if r1 > mid:
return self._query(node * 2 + 1, mid + 1, r, r1, r2, c1, c2)

left_val = self._query(node * 2, l, mid, r1, r2, c1, c2)
right_val = self._query(node * 2 + 1, mid + 1, r, r1, r2, c1, c2)
return max(left_val, right_val)

def count_local_maximums(matrix: List[List[int]]) –> int:
"""
计算矩阵中局部最大值的数量
"""
if not matrix or not matrix[0]:
return 0

n, m = len(matrix), len(matrix[0])

# 构建线段树
seg_tree = SegmentTree(matrix)

ans = 0

for i in range(n):
for j in range(m):
x = matrix[i][j]
if x == 0:
continue

# 计算需要检查的四个区域
# 区域1：行范围 [i-x, i+x]，列范围 [j-x+1, j+x]
# 区域2：行范围 [i-x+1, i+x-1]，列范围 [j-x, j+x+1]
# 注意：排除四个角
# 实际上原Go代码用两次查询做了覆盖，我们保持一致

r1_1 = max(i – x, 0)
r2_1 = min(i + x, n – 1)
c1_1 = max(j – x + 1, 0)
c2_1 = min(j + x, m – 1)

r1_2 = max(i – x + 1, 0)
r2_2 = min(i + x – 1, n – 1)
c1_2 = max(j – x, 0)
c2_2 = min(j + x + 1, m – 1)

# 查询两个区域的最大值
max1 = seg_tree.query(r1_1, r2_1, c1_1, c2_1)
max2 = seg_tree.query(r1_2, r2_2, c1_2, c2_2)

if max(max1, max2) <= x:
ans += 1

return ans

def main():
"""测试用例"""
matrix = [
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]
]

result = count_local_maximums(matrix)
print(result)

if __name__ == "__main__":
main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

// 一维ST表模板
template<typename T>
class SparseTable {
private:
vector<vector<T>> st;
T (*op)(T, T);

public:
SparseTable() {}

SparseTable(const vector<T>& arr, T (*operation)(T, T)) : op(operation) {
int n = arr.size();
if (n == 0) return;

int k = 0;
while ((1 << k) <= n) k++;
st.resize(k, vector<T>(n));

// 初始化第0层
for (int i = 0; i < n; i++) {
st[0][i] = arr[i];
}

// 构建ST表
for (int i = 1; i < k; i++) {
int len = 1 << i;
int half = len >> 1;
for (int j = 0; j + len <= n; j++) {
st[i][j] = op(st[i–1][j], st[i–1][j + half]);
}
}
}

// 查询闭区间 [l, r]
T query(int l, int r) const {
if (l > r) {
// 返回一个极小值
if constexpr (is_same<T, int>::value) {
return INT_MIN;
}
return T();
}
int length = r – l + 1;
int k = 0;
while ((1 << (k + 1)) <= length) k++;
return op(st[k][l], st[k][r – (1 << k) + 1]);
}
};

// 线段树类
class SegmentTree {
private:
vector<vector<int>>& matrix;
int n, m;
vector<SparseTable<int>> tree;
int size;

// 合并两个数组，按列取最大值
vector<int> mergeColumns(const vector<int>& left, const vector<int>& right) {
vector<int> result(m);
for (int i = 0; i < m; i++) {
result[i] = max(left[i], right[i]);
}
return result;
}

void build(int node, int l, int r) {
if (l == r) {
// 叶子节点：直接使用该行的ST表
tree[node] = SparseTable<int>(matrix[l], [](int a, int b) { return max(a, b); });
return;
}

int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);

// 合并左右子树：对每一列取最大值
vector<int> merged(m);
for (int i = 0; i < m; i++) {
merged[i] = max(tree[node * 2].query(i, i), tree[node * 2 + 1].query(i, i));
}
tree[node] = SparseTable<int>(merged, [](int a, int b) { return max(a, b); });
}

int queryRec(int node, int l, int r, int r1, int r2, int c1, int c2) const {
if (r1 <= l && r <= r2) {
return tree[node].query(c1, c2);
}

int mid = (l + r) / 2;
if (r2 <= mid) {
return queryRec(node * 2, l, mid, r1, r2, c1, c2);
}
if (r1 > mid) {
return queryRec(node * 2 + 1, mid + 1, r, r1, r2, c1, c2);
}

int left_val = queryRec(node * 2, l, mid, r1, r2, c1, c2);
int right_val = queryRec(node * 2 + 1, mid + 1, r, r1, r2, c1, c2);
return max(left_val, right_val);
}

public:
SegmentTree(vector<vector<int>>& mat) : matrix(mat) {
n = matrix.size();
m = matrix[0].size();

// 计算线段树大小
size = 1;
while (size < n) size <<= 1;
tree.resize(size * 2);

build(1, 0, n – 1);
}

int query(int r1, int r2, int c1, int c2) const {
if (r1 > r2 || c1 > c2) {
return INT_MIN;
}
return queryRec(1, 0, n – 1, r1, r2, c1, c2);
}
};

int countLocalMaximums(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}

int n = matrix.size();
int m = matrix[0].size();

// 构建线段树
SegmentTree segTree(matrix);

int ans = 0;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = matrix[i][j];
if (x == 0) continue;

// 计算两个需要查询的区域
// 区域1：行范围 [i-x, i+x]，列范围 [j-x+1, j+x]
// 区域2：行范围 [i-x+1, i+x-1]，列范围 [j-x, j+x+1]

int r1_1 = max(i – x, 0);
int r2_1 = min(i + x, n – 1);
int c1_1 = max(j – x + 1, 0);
int c2_1 = min(j + x, m – 1);

int r1_2 = max(i – x + 1, 0);
int r2_2 = min(i + x – 1, n – 1);
int c1_2 = max(j – x, 0);
int c2_2 = min(j + x + 1, m – 1);

// 查询两个区域的最大值
int max1 = segTree.query(r1_1, r2_1, c1_1, c2_1);
int max2 = segTree.query(r1_2, r2_2, c1_2, c2_2);

if (max(max1, max2) <= x) {
ans++;
}
}
}

return ans;
}

int main() {
vector<vector<int>> matrix = {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 2, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};

int result = countLocalMaximums(matrix);
cout << result << endl;
return 0;
}