思路
主要在于每次通过数组 arr 中的值，进行将 “0“ 变为 ”1“，从而寻找出现连续的 1 值，问题就在于如何记录此时所出现的连续的 “1” 的字符串的长度。 （注意，这里不能再去循环遍历，肯定会超时。）
前置
n 表示数组的长度
方案一
参照 [Python] Clean Union-Find solution with explanation - O(N))
在 “0” 变为 “1” 的过程中，之后就需要对存在的连续的 “1” 进行合并。这里就想到了 unionset 。在 unionset 进行 union 的过程中，需要考虑 union 后连续的 “1” 的长度的问题。所以这里使用了 rank 数组来记录，合并后连续 “1” 的长度值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| from typing import List
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n + 1)]
self.rank = [0] * (n + 1)
def find(self, s):
if self.parent[s] == s:
return s
self.parent[s] = self.find(self.parent[s])
return self.parent[s]
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if a > b:
a, b = b, a
self.parent[b] = a
self.rank[a] += self.rank[b]
return True
class Solution:
def findLatestStep(self, arr: List[int], M: int) -> int:
if len(arr) == M:
return M
uf = UnionFind(len(arr))
ans = -1
for i, num in enumerate(arr):
uf.rank[num] = 1
for j in (num - 1, num + 1):
if 0 < j <= len(arr):
if uf.rank[uf.find(j)] == M:
ans = i
if uf.rank[j]:
uf.union(num, j)
return ans
|
方案二
逆向考虑，将数组中的值逆向插入到 [ 0, n + 1] 的数组中。
此时的操作，代表着将连续的 1 中的一项，修改为 ”0”。而根据其在数组左右两项的值做差，可求得其左右的连续的 “1” 的长度。
举例：[ 3, 5, 1, 2, 4]， 要插入的数组为 [0, 6]
1. 插入 4， 结果为 [0, 4, 6] ，左边连续的 “1” 的长度为 4 - 0 - 1 = 3，右边连续的 “1” 的长度为 6- 4 - 1 = 1
2. 插入 2, 结果为 [0, 2, 4, 6] 左边连续的 “1” 的长度为 4 - 2 - 1 = 1，右边连续的 “1” 的长度为 2 - 0 - 1 = 1
3. …
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def findLatestStep(self, arr: List[int], M: int) -> int:
n = len(arr)
if M == n:
return n
lis = [0, n + 1]
for num in arr[::-1]:
import bisect
index = bisect.bisect(lis, num)
lis.insert(index, num)
right = lis[index + 1] - num - 1
if right == M:
return n - 1
left = num - lis[index-1] - 1
if left == M:
return n - 1
n -= 1
return -1
|
方案三
参照 lee215) 大佬的答案
记录分析影响的左右边界的 长度值。
使用两个数组进行更新记录：
length 数组记录当前更新范围连续 “1” 的长度
Count 记录每个长度出现的次数。最后一次出现的次数即为所求的值。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def findLatestStep(self, arr: List[int], M: int) -> int:
n = len(arr)
length = [0] * (n + 2)
count = [0] * (n + 1)
res = -1
for i, num in enumerate(arr):
left = length[num - 1]
right = length[num + 1]
length[num] = length[num - left] = length[num + right] = left + right + 1
count[left] -= 1
count[right] -= 1
count[length[num]] += 1
if count[M]:
res = i + 1
return res
|
