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
}