DeepSeek LeetCode 2503.矩阵查询可获得的最大分数 Go实现

以下是 LeetCode 2503 的 Go 实现使用优先队列 排序 离线查询的思路goimport (container/heapsort)type Cell struct {val intr intc int}// 最小堆实现type MinHeap []Cellfunc (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 : *hn : 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] trueheap.Push(pq, Cell{grid[0][0], 0, 0})res : make([]int, k)count : 0dirs : [][]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] trueheap.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)示例运行gogrid : [][]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 包和排序功能。