DeepSeek LeetCode 2503.矩阵查询可获得的最大分数 Go实现
以下是 LeetCode 2503 的 Go 实现,使用优先队列 + 排序 + 离线查询的思路:
```go
import (
"container/heap"
"sort"
)
type Cell struct {
val int
r int
c int
}
// 最小堆实现
type MinHeap []Cell
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(Cell))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0:n-1]
return x
}
func maxPoints(grid [][]int, queries []int) []int {
m, n := len(grid), len(grid[0])
k := len(queries)
// 记录原始索引并排序
qs := make([][2]int, k)
for i := 0; i < k; i++ {
qs[i] = [2]int{queries[i], i}
}
sort.Slice(qs, func(i, j int) bool {
return qs[i][0] < qs[j][0]
})
// 最小堆
pq := &MinHeap{}
heap.Init(pq)
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
// 从起点开始
visited[0][0] = true
heap.Push(pq, Cell{grid[0][0], 0, 0})
res := make([]int, k)
count := 0
dirs := [][]int{{1,0},{-1,0},{0,1},{0,-1}}
for _, q := range qs {
val, idx := q[0], q[1]
// 扩展所有值小于当前查询的单元格
for pq.Len() > 0 && (*pq)[0].val < val {
cell := heap.Pop(pq).(Cell)
count++
// 探索四个方向
for _, d := range dirs {
nr, nc := cell.r + d[0], cell.c + d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] {
visited[nr][nc] = true
heap.Push(pq, Cell{grid[nr][nc], nr, nc})
}
}
}
res[idx] = count
}
return res
}
```
核心要点
1. 最小堆:存储 (值, 行, 列),按网格值排序
2. 离线处理:将 queries 排序并保留原始索引
3. BFS扩展:只扩展值小于当前查询的单元格
4. 访问标记:每个单元格只入队一次
复杂度分析
· 时间复杂度:O(mn log(mn) + k log k)
· 每个单元格入堆一次:O(mn log(mn))
· 查询排序:O(k log k)
· 空间复杂度:O(mn + k)
示例运行
```go
grid := [][]int{{1,2,3},{2,5,7},{3,5,1}}
queries := []int{5,6,1}
result := maxPoints(grid, queries)
// 输出: [4,7,1]
```
这个实现能够高效地处理题目要求,利用了 Go 的 container/heap 包和排序功能。
更多推荐



所有评论(0)