2026-08-26：矩阵中的局部最大值Ⅱ。用go语言，给定一个大小为 n 行 m 列的整数矩阵，矩阵里所有数字都是大于等于 0 的。
对于矩阵中任意一个数值大于 0 的格子（称为“当前格子”），我们以它的数值作为半径，检查它周围的一个特定区域：
• 这个区域包括：以当前格子为中心，向上、下、左、右各延伸“当前数值”那么多行的所有格子。
• 但是，要排除那些行方向和列方向的距离都恰好等于当前数值的格子（也就是四个角上的最远点）。
• 同时，超出矩阵边界的格子不纳入考虑。
如果当前格子满足以下两个条件，就称它为“局部最大值”：
1. 它本身的值大于 0；
2. 在上述所有被考虑的格子中，没有任何一个格子的数值比当前格子的数值更大（也就是当前格子的值是这些考虑范围内的最大值，允许相等）。
最后，你需要统计整个矩阵中这样的“局部最大值”一共有多少个，并返回这个数量。
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表代表某段连续行在每一列上的最大值。
• 输入一个数组
a和合并函数op（这里是 max）。• 构建
st二维数组，st[k][j]表示从 j 开始长度为2^k的区间的最大值。• 查询
query(l, r)时，利用bits.Len8快速得到区间长度对应的 k，然后合并两个重叠区间取最大值。• 这里因为数据范围 ≤ 200，使用
bits.Len8是安全的。
• 线段树每个节点代表一个行区间 [l, r]。
• 叶子节点：直接对
matrix[l]（一行）建立一维ST表。• 内部节点：
• 先分别构建左右子树。
• 取左右子树根节点（即对应行区间）的
st[0]（长度为 m 的数组）逐列取最大值，形成新的长度为 m 的数组。• 再对这个新数组建立一维ST表。
这样，每个线段树节点就保存了该行区间内，每一列的最大值，并且支持快速查询任意列区间。
第四步：查询过程
对于每个格子(i, j)，值x：
• 我们要检查两个矩形区域的最大值：
1.区域A：行范围
[max(i-x, 0), min(i+x, n-1)]，列范围[max(j-x+1, 0), min(j+x, m)]（注意列左边少1，右边含j+x，从而避开四个角中的左右角）。2.区域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(node, l, r, r1, r2, c1, c2)：
•
node：当前节点，管理行区间 [l, r]。•
[r1, r2]：要查询的行范围。•
[c1, c2)：要查询的列范围（左闭右开）。• 如果当前节点完全被
[r1, r2]包含，则直接返回该节点上ST表对列区间的查询结果。• 否则，根据
[r1, r2]与左右子树的交集，递归查询左右子树，并取最大值返回。
1. 获取矩阵大小
n, m。2. 构建线段树，大小根据
n计算（2 << bits.Len(uint(n-1))）。3. 调用
build填充线段树。4. 双重循环遍历所有格子：
• 只处理值 > 0 的格子。
• 计算两个区域的行列范围。
• 查询两个区域的最大值。
• 如果二者均 ≤ 当前值，则 ans++。
5. 输出 ans。
第七步：例子验证
给定全 0 矩阵，中间一个 2：
• 对于 (3,3)，x=2：
• 区域A：行[1,5]，列[2,5]（排除左上角(1,1)和右上角(1,5)）
• 区域B：行[2,4]，列[1,6]（排除左下角(5,1)和右下角(5,5)）
• 这两个区域合起来就是除了四个角之外的整个 5x5 方形。
• 全部为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<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<
}
// 完整模板见 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 < 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++完整代码如下：
using namespace std;
// 一维ST表模板
template
class SparseTable {
private:
vector > st;
T (*op)(T, T);
public:
SparseTable() {}
SparseTable(const vector & 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 (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 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 int >>& matrix;
int n, m;
vector 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 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 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 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 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴