1562. Find Latest Group of Size M

题目信息

题号:

1562

难度:

Medium

主题:

数组、区间合并、并查集

原题:

LeetCode 1562

重点:

长度为 n 的二进制串初始全零,第 i 步把 arr[i] 位置置一;求最后存在长度恰好为 m 的连续一段的步骤

题目重述

给定 1 到 n 的一个排列 arr。初始二进制字符串长度为 n 且全部为 0。第 i 步把一基位置 arr[i] 设置为 1,已经设置的位不会恢复为零。

请返回最后一个仍存在长度恰好为 m 的连续一段的步骤编号,步骤从 1 开始。若从未出现,返回 -1。

1 <= m <= n == arr.length <= 10^5。

自建示例

目标长度的段可能随后与相邻段合并而消失:

输入:arr = [3,1,4,2,5], m = 2
输出:3
解释:第三步位置 3、4 形成长度 2 的段;第四步后它扩展为长度 4。

目标长度等于整个字符串时最后一步必然满足:

输入:arr = [2,1,3], m = 3
输出:3
解释:第三步所有位置都变为 1,形成长度 3 的唯一连续段。