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
}