2503. Maximum Number of Points From Grid Queries
忘了是哪一天的每日
priority queue + difference array 的組合
想法就先把queries按照大小排好
從[0,0]開始每次都挑最小的grid[i][j]走
這樣可以保證到任意grid[i][j]的路徑上最大的值為最小
所以要記錄這條路徑的最大值
到每一個cell就去搜尋這條路徑的最大值會排在queries的哪個位置
假設排在idx
那difference array[idx]就加1
最後把difference array加起來得到每個queries的最大points
並照原本的順序排列就好
golang code :
type node struct {
coordinate [2]int
maxVal int
}
type minHeap []node
func (this minHeap) Len() int { return len(this) }
func (this minHeap) Less(i, j int) bool { return this[i].maxVal < this[j].
maxVal }
func (this minHeap) Swap(i, j int) { this[i], this[j] = this[j], this[i]
}
func (this *minHeap) Push(x interface{}) { *this = append(*this, x.(node)) }
func (this *minHeap) Pop() interface{} {
n := len(*this)
res := (*this)[n-1]
(*this) = (*this)[:n-1]
return res
}
func maxPoints(grid [][]int, queries []int) []int {
n, m, k := len(grid), len(grid[0]), len(queries)
queriesIdx := make([]int, k)
for key := range queries {
queriesIdx[key] = key
}
slices.SortFunc(queriesIdx, func(i, j int) int { return queries[i] - queries[
j] })
slices.Sort(queries)
array, visited, direction := make([]int, k+1), make([]bool, n*m), [][2]int{{1
, 0}, {-1, 0}, {0, 1}, {0, -1}}
h := minHeap{node{[2]int{0, 0}, grid[0][0]}}
visited[0] = true
for h.Len() > 0 {
curNode := heap.Pop(&h).(node)
x, y, curMax := curNode.coordinate[0], curNode.coordinate[1], curNode.maxVal
i := sort.SearchInts(queries, curMax+1)
array[i]++
for _, val := range direction {
nexX, newY := x+val[0], y+val[1]
tmp := nexX*m + newY
if newY > -1 && nexX > -1 && newY < m && nexX < n && !visited[tmp] {
heap.Push(&h, node{[2]int{nexX, newY}, max(curMax, grid[nexX][newY])})
visited[tmp] = true
}
}
}
cnt, ans := 0, make([]int, k)
for key, val := range queriesIdx {
cnt += array[key]
ans[val] = cnt
}
return ans
}