查找大小为 M 的最新分组

标签: 数组 二分查找 模拟

难度: Medium

给你一个数组 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

Submission

运行时间: 129 ms

内存: 27.3 MB

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        if m == n:
            return n
        cnt = [0] * (n + 2)
        ans = -1
        for i, v in enumerate(arr):
            v -= 1
            l, r = cnt[v - 1], cnt[v + 1]
            if l == m or r == m:
                ans = i
            cnt[v - l] = cnt[v + r] = l + r + 1
        return ans

Explain

本题的核心思路是使用一个额外的数组 `cnt` 来记录每个位置的连续 '1' 的长度。数组 `cnt` 的长度为 `n + 2`，其中 `n` 是输入数组 `arr` 的长度。这样设置可以避免处理边界情况。\n\n过程如下：\n1. 遍历数组 `arr`，每个元素 `v` 对应的是将二进制字符串的第 `v-1` 位置设为 '1'。\n2. 对于每个 `v`，检查其左侧和右侧的连续 '1' 的长度，存储在变量 `l` 和 `r` 中。这些长度可以从 `cnt` 数组获得。\n3. 如果左侧或右侧的长度恰好为 `m`，则更新答案 `ans` 为当前步骤编号 `i`（从0开始计数）。\n4. 更新 `cnt` 数组，将新形成的连续 '1' 的长度记录在 `cnt[v-l]` 和 `cnt[v+r]` 中。\n5. 特殊情况是当 `m` 等于 `n` 时，按照题目的逻辑，只有当所有位都是 '1' 时，才返回 `n`。\n\n该方法避免了直接检查整个字符串的高开销，而是通过局部更新和记录来保持整体的连续区间长度信息。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        if m == n:
            return n  # 如果 m 等于 n，返回 n，因为只有最后一步所有位置都是 '1'
        cnt = [0] * (n + 2)  # 初始化长度为 n+2 的数组，额外的两个元素用于处理边界
        ans = -1
        for i, v in enumerate(arr):
            v -= 1  # 将 v 转换为从 0 开始的索引
            l, r = cnt[v - 1], cnt[v + 1]  # 获取左右两边的连续 '1' 的长度
            if l == m or r == m:
                ans = i  # 如果左侧或右侧长度为 m，更新答案
            cnt[v - l] = cnt[v + r] = l + r + 1  # 更新新的连续区间长度信息
        return ans

Explore

在更新cnt数组时，只有两个位置cnt[v-l]和cnt[v+r]被更改，这两个位置分别表示整个连续'1'序列的起始和结束位置。更新这两个边界的原因是，只有这两个位置的值会影响到新加入的'1'如何改变整个连续序列的计数。由于连续序列的内部元素的cnt值不会被直接查询（只查询边界），因此更新边界不会影响其他位置的正确性。同时，这种方式确保了只有边界的连续长度被更新，保持了算法的效率和准确性。

题目要求找到最后一次出现恰好长度为m的连续'1'的步骤。在算法中，每次操作都会检查插入点的左右连续'1'的长度是否为m。如果是，说明在这一步操作完成后，恰好有一个长度为m的连续'1'序列。因此，可以直接更新答案为当前步骤i。此外，如果后续的操作影响了这个连续序列，即使它再次变为m，也会在后面的步骤中被检测到并更新答案。

如果m等于n，意味着只有在数组arr的所有元素都被填充为'1'且完全填满整个数组时，才符合条件。无论arr的顺序如何，只要最后一个操作将最后一个'0'变为'1'，整个数组就全是'1'。因此，不论arr的顺序如何，最后一个操作总是第n步，所以返回n是正确的。

在算法中，每次插入都会检查并更新答案ans，如果存在多个长度为m的连续'1'组，算法会在发现第一个这样的组时更新答案。之后的操作可能会改变这些连续序列的长度，但每次操作都会重新评估并可能更新答案。因此，即使存在多个长度为m的连续序列，算法依然能够正确记录最后一次出现长度为m的步骤，不会影响最终答案的正确性。