每日一题 1488. 避免洪水泛滥（中单，贪心，二分）

本文主要是介绍每日一题 1488. 避免洪水泛滥（中单，贪心，二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

1. 当某一天为晴天，可以选择抽水时，我们是不知道要抽哪一个的，最优解应该是抽接下来最近的要发洪水的湖泊，所以我们先把晴天的坐标保存下来，需要用的时候再拿出来
2. 需要注意的是，只有晴天发生在两次下雨之间，才可以把这天从晴天数组中取出来抽水，因此当遍历至第 i 天，且会导致 rains[i] 会发洪水是，应从晴天数组中寻找距离 rains[i] 上次下雨之后的最近的那一天来抽 rains[i] 的水，如果找不到这样子的一天，那么洪水就无法避免，同样的晴天数组为空，洪水也无法避免
3. 在查找晴天时，由于晴天数组是有序的，所以可以二分查找缩短时间
4. 存在疑问，当设置晴天数组为 list 时，list 的 pop(n) 操作是O(n)的，会导致消耗时间奇高，但如果设置为 deque() ，同样的耗时O(n) 的 remove() 操作却可以耗时击败 100%

class Solution:def avoidFlood(self, rains: List[int]) -> List[int]:n = len(rains)ans = [-1] * nnow = {}c = deque()for i in range(n):if rains[i] == 0:c.append(i)elif rains[i] not in now:now[rains[i]] = ielif len(c) > 0:ind = bisect_left(c, now[rains[i]])if ind == len(c):return []else:now[rains[i]] = ians[c[ind]] = rains[i]c.remove(c[ind])else:return []for i in c:ans[i] = 1return ans

这篇关于每日一题 1488. 避免洪水泛滥（中单，贪心，二分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---