题目描述

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

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

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

返回存在长度 恰好 为 m 的 一组 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。

输入：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。

输入：arr = [1], m = 1
输出：1

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

限制

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

算法

(并查集，哈希表) $O(n)$

1. 直接按照题目描述做，1 到 n 每个位置看做一个点，初始化并查集，且每个点的初始大小为 1。设立 0 和 n+1 两个哨兵位置，大小为 0。
2. 初始化一个哈希表，记录当前不同长度的 连续 1 组 的个数，每个点所在集合的大小相当于连续 1 的长度。
3. 遍历 arr 数组，当前位置 v 标记为 1，然后哈希表中 1 的个数加 1，接下来判断 v 左右两边的情况。
4. 如果 v-1 被标记为 1，则 v-1 与 v 合并；然后如果 v+1 被标记为 1 则合并 v 与 v+1。合并过程中，首先在哈希表中将双方集合的大小的个数减 1，然后双方集合大小求和的个数加 1。。
5. 遍历过程中，每次都判断哈希表中 m 的值是否大于 0，如果大于 0 则记录当前下标。

时间复杂度

• 遍历数组一次，并查集的操作时间近似为常数，哈希表的操作时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储并查集数组和哈希表。

Go 代码

var f, sz []int
var seen map[int]int

func findLatestStep(arr []int, m int) int {
    n := len(arr)
    f = make([]int, n+2)
    sz = make([]int, n+2)

    for i := 1; i <= n; i++ {
        f[i], sz[i] = i, 1
    }

    visited := make([]bool, n+2)
    seen = make(map[int]int)
    ans := -1
    for i, v := range arr {
        visited[v] = true
        seen[1]++

        if visited[v-1] {
            merge(v-1, v)
        }
        if visited[v+1] {
            merge(v+1, v)
        }

        if seen[m] > 0 {
            ans = i + 1
        }
    }

    return ans
}

func merge(x, y int) {
    fx, fy := find(x), find(y)
    if fx == fy {
        return
    }
    seen[sz[fx]]--
    seen[sz[fy]]--
    seen[sz[fx]+sz[fy]]++

    if sz[fx] < sz[fy] {
        f[fx] = fy
        sz[fy] += sz[fx]
    } else {
        f[fy] = fx
        sz[fx] += sz[fy]
    }
}

func find(x int) int {
    if x == f[x] {
        return x
    }
    f[x] = find(f[x])
    return f[x]
}