python学习笔记4-二分查找

题目链接

• 一个List对象可以 ‘.bisect(val)’ 获得大于等于val的最小元素
• 这道题目思想值得看一下

from sortedcontainers import SortedList
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        ans = [1] * len(rains)
        l = SortedList()    # 可以清空池子的天
        mp = {} # 当前哪一个池子是满的
        for i, rain in enumerate(rains):
            if rain == 0:
                l.add(i)    # 没有下雨，则这一天可以用来清空
            else:
                ans[i] = -1
                if rain in mp: # 如果rain这一个池子是满的，则需要在第mp[rain]天之后的一天清空
                    it = l.bisect(mp[rain])
                    if it == len(l):
                        return []
                    empty_day = l[it]
                    ans[empty_day] = rain
                    l.discard(empty_day)
                mp[rain] = i
        return ans

                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22