LeetCode 题解工作台
查找大小为 M 的最新分组
给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。 在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。 给…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
正向遍历 ，利用并查集动态维护每组 的长度。 时间复杂度 $O(n \times \log n)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个数组 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.length1 <= n <= 10^51 <= arr[i] <= narr中的所有整数 互不相同1 <= m <= arr.length
解题思路
class Solution:
def findLatestStep(self, arr: List[int], m: int) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa == pb:
return
p[pa] = pb
size[pb] += size[pa]
n = len(arr)
if m == n:
return n
vis = [False] * n
p = list(range(n))
size = [1] * n
ans = -1
for i, v in enumerate(arr):
v -= 1
if v and vis[v - 1]:
if size[find(v - 1)] == m:
ans = i
union(v, v - 1)
if v < n - 1 and vis[v + 1]:
if size[find(v + 1)] == m:
ans = i
union(v, v + 1)
vis[v] = True
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity can be O(n) since each position is updated at most once, and hash lookups are O(1). Space complexity is O(n) to store group boundaries and counts of groups of specific lengths. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if groups can merge or split dynamically and how to track that efficiently.
- question_mark
Questions whether scanning from the end helps in quickly finding the latest step.
- question_mark
Checks understanding of hash-based bookkeeping for constant-time group length updates.
常见陷阱
外企场景- error
Failing to update both ends of a merged group, leading to incorrect group length tracking.
- error
Counting overlapping groups incorrectly, especially after merges or splits.
- error
Assuming the first occurrence is enough instead of tracking the latest step.
进阶变体
外企场景- arrow_right_alt
Find the earliest step a group of size m exists instead of the latest.
- arrow_right_alt
Return the number of steps where at least one group of size m exists.
- arrow_right_alt
Change the problem to track groups of at least size m instead of exact size.