以下是 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 包和排序功能。

 

Logo

中国智能体开发者社区,聚焦智能体与大模型开发,提供前沿资讯、实用工具链、开源项目及行业案例。通过技术沙龙、开发者大赛等活动,促进经验交流与协作,助力开发者快速构建创新智能应用。

更多推荐