leetcode 1562. 查找大小为 M 的最新分组

给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。

在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。

给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。

返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。

示例 1：

输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1：“00100”，由 1 构成的组：[“1”]
步骤 2：“00101”，由 1 构成的组：[“1”, “1”]
步骤 3：“10101”，由 1 构成的组：[“1”, “1”, “1”]
步骤 4：“11101”，由 1 构成的组：[“111”, “1”]
步骤 5：“11111”，由 1 构成的组：[“11111”]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。
示例 2：

输入：arr = [3,1,5,4,2], m = 2
输出：-1
解释：
步骤 1：“00100”，由 1 构成的组：[“1”]
步骤 2：“10100”，由 1 构成的组：[“1”, “1”]
步骤 3：“10101”，由 1 构成的组：[“1”, “1”, “1”]
步骤 4：“10111”，由 1 构成的组：[“1”, “111”]
步骤 5：“11111”，由 1 构成的组：[“11111”]
不管是哪一步骤都无法形成长度为 2 的一组 1 。
示例 3：
输入：arr = [1], m = 1
输出：1

示例 4：
输入：arr = [2,1], m = 2
输出：2

提示：
n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
arr 中的所有整数 互不相同
1 <= m <= arr.length

思路，可以用合并区间的思路，需要注意的是，区间合并时，只用更新区间最左边和最右边的 index，因为合并区间的中间不会被访问到

class Solution:

    ## 时间复杂度为 O(n), 对相邻的集合进行合并
    def findLatestStep(self, arr: List[int], m: int) -> int:
        if m == len(arr):
            return m
        ### 从后往前检索, 每次合并连续的
        nums = [(-1, -1)] * (len(arr)+1)
        count, res = 0, -1
        for i in range(len(arr)):
            left_1, right_2 = arr[i], arr[i]
            ## 左边处理
            if nums[arr[i]-1][0] != -1:
                left_1, left_2 = nums[arr[i]-1][0], nums[arr[i]-1][1]
                if left_2 - left_1 + 1 == m:
                    count -= 1

            ## 右边
            if arr[i] < len(arr) and nums[arr[i]+1][0] != -1:
                right_1, right_2 = nums[arr[i]+1][0], nums[arr[i]+1][1]
                if right_2 - right_1 + 1 == m:
                    count -= 1
            ## 更新nums 中组中的 最左边和最右边的 index
            ## 因为 [left_1, right_2] 属于同一个分组了, 后续遍历不会访问到其中间的 index, 中间 index 对应的 nums 不用修改
            group_len = right_2 - left_1 + 1
            if group_len == m:
                count += 1
            if count > 0:
                res = i+1
            nums[left_1] = (left_1, right_2)
            nums[right_2] = (left_1, right_2)
        return res
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