1562. Find Latest Group of Size M¶
题目信息¶
- 题号:
1562
- 难度:
Medium
- 主题:
数组、区间合并、并查集
- 原题:
- 重点:
长度为
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 的唯一连续段。