4116. 下雨天安排伞
难度简单
题目描述
给你一个长度为 n 的 二进制数组 rain,其中 rain[i] == 1 表示第 i 天下雨,rain[i] == 0 表示第 i 天不下雨。
Alice 和 Bob 在这 n 天里共用 一把伞。在每一天 i:
- 对于
0 <= i < n - 1,如果rain[i] == rain[i + 1] == 1,则 Alice 在第i天需要伞。 - 如果
rain[i] == 1,则 Bob 需要伞。 - 他们之中 至多一人 可以得到伞。
- 如果只有一个人需要伞,则由这个人得到伞。
- 如果 两人 都需要伞,则伞归目前为止得到伞次数 较少 的人。如果次数 相同,则伞归 Alice。
- 如果两人都不需要伞,则没有人得到伞。
一个人的计数只有在其得到伞的那一天才会 增加。初始时,两人的计数均为 0。
返回一个长度为 n 的字符串数组 answer,其中 answer[i] 为 "Alice"、"Bob" 或 "None",表示第 i 天得到伞的人。
二进制数组 是只包含 0 和 1 的数组。
示例 1:
输入: rain = [1,1,0,1,1]
输出: ["Alice","Bob","None","Alice","Bob"]
解释:
- 第 0 天:
rain[0] == 1且rain[1] == 1,所以两人都需要伞。计数相同,所以 Alice 得到伞。 - 第 1 天:
rain[1] == 1,所以 Bob 需要伞,但rain[2] == 0,所以 Alice 不需要伞。因此 Bob 得到伞。 - 第 2 天:没有下雨,所以没有人得到伞。
- 第 3 天:
rain[3] == 1且rain[4] == 1,所以两人都需要伞。计数均为 1,相同,所以 Alice 得到伞。 - 第 4 天:最后一天,所以只有 Bob 需要伞,由他得到伞。
- 因此,
answer = ["Alice", "Bob", "None", "Alice", "Bob"]。
示例 2:
输入: rain = [0,1,0,1]
输出: ["None","Bob","None","Bob"]
解释:
- 从未出现连续两天下雨的情况,所以 Alice 从不需要伞。
- Bob 在第 1 天和第 3 天得到伞,第 0 天和第 2 天没有人得到伞。
- 因此,
answer = ["None", "Bob", "None", "Bob"]。
提示:
1 <= n == rain.length <= 100rain[i]为 0 或 1。
解法
方法一:模拟
思考
\(n\) 不超过 \(100\),按天决定伞给谁即可。次数只在真正拿到伞时增加,两人同时需要时要比此前的次数,所以必须从左往右扫描。
Alice 需要伞,当且仅当当天和后一天都下雨。当天已经下雨,Bob 也一定需要,Alice 不会单独需要。
因此只维护已经拿到伞的次数 \(a\) 和 \(b\)。先用当前次数判断归属,再给拿到伞的人加一,后一天是否下雨决定 Alice 会不会进入这次比较。
我们用 \(a\) 和 \(b\) 分别记录 Alice 与 Bob 已经拿到伞的次数,初始都为 \(0\),并从左到右扫描 \(\textit{rain}\)。
第 \(i\) 天若 \(\textit{rain}[i]=0\),没有人需要伞,答案为 \(\text{None}\)。若 \(\textit{rain}[i]=1\),Bob 需要伞。当 \(i<n-1\) 且 \(\textit{rain}[i+1]=1\) 时 Alice 也需要伞;若此时 \(a\le b\),伞给 Alice, \(a\) 加一,否则伞给 Bob, \(b\) 加一。后一天不下雨,或当天已是最后一天时,只有 Bob 需要伞,同样记给 Bob。
时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |