Re: [閒聊] 每日leetcode

看板Marginalman作者JIWP (神楽めあ的錢包)時間1月前 (2025/10/08 00:05)推噓0(0推 0噓 0→)

1488. Avoid Flood in The City 思路: 當rain[i] = 0, 把i丟到minimum heap裡面並且用一個map紀錄出現過的lake在rains裡的index 當這個rains[i](lake)沒出現過, answer[i]就填-1, 並且用map記錄lake的index 如果這個rains[i](lake)有出現過, 就看minimum heap裡面有沒有大於i的index 找出第一個大於i的index, 並且answer[index] = rains[i]、answer[i]=-1 然後更新map[rains[i]] = i 如果minimum heap中沒有index大於i就回傳空矩陣 golang code: type minHeap []int func (this minHeap) Len() int { return len(this) } func (this minHeap) Less(i, j int) bool { return this[i] < this[j] } 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.(int)) } func (this *minHeap) Pop() interface{} { n := len(*this) res := (*this)[n-1] *this = (*this)[:n-1] return res } func avoidFlood(rains []int) []int { n := len(rains) ans := make([]int, n) zeroIdx := minHeap{} flood := make(map[int]int) for i := 0; i < n; i++ { ans[i] = 1 if rains[i] == 0 { heap.Push(&zeroIdx, i) } else { if _, ok := flood[rains[i]]; ok { tmp := []int{} for zeroIdx.Len() > 0 && zeroIdx[0] < flood[rains[i]] { tmp = append(tmp, heap.Pop(&zeroIdx).(int)) } if zeroIdx.Len() == 0 { return []int{} } idx := heap.Pop(&zeroIdx).(int) ans[idx] = rains[i] ans[i] = -1 flood[rains[i]] = i for _, val := range tmp { heap.Push(&zeroIdx, val) } } else { flood[rains[i]] = i ans[i] = -1 } } } return ans } -- https://i.imgur.com/r9FBAGO.gif