leetcode：1562. 查找大小为 M 的最新分组【模拟 + 端点记录 + 范围合并】

分析

建立数字points
每个元素代表的是第几个位置的含1的连续段的开头和结尾
然后每加入一个新的相当于从0变1，考虑和左边和右边的合并
可能会剪掉两个合理的块
以及可能会加上一个合理的块
最后如果存在M的1块，可以计入结果
最后更新两个端点的left和right即可
因为中间的不可能再被用到~

ac code

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        # 模拟
        n = len(arr)
        # fuck[i]表示包含i在内的连续1的最左侧和最右侧
        # [1..n]
        fuck = [(-1, -1) for _ in range(n + 1)]

        cntM = 0
        ans = -1

        for i in range(n):
            # 初次来到
            left = right = arr[i]
            # 左侧1合并
            if arr[i] >= 1 and fuck[arr[i] - 1][1] != -1:
                # 更新left
                left = fuck[arr[i] - 1][0]
                # 更新cntM
                if fuck[arr[i] - 1][1] - fuck[arr[i] - 1][0] + 1 == m:
                    cntM -= 1
            # 右侧1合并
            if arr[i] < n and fuck[arr[i] + 1][0] != -1:
                # 更新right
                right = fuck[arr[i] + 1][1]
                # 更新cntM
                if fuck[arr[i] + 1][1] - fuck[arr[i] + 1][0] + 1 == m:
                    cntM -= 1
            
            if right - left + 1 == m:
                cntM += 1
            
            if cntM > 0:
                ans = i + 1
            
            fuck[left] = fuck[right] = (left, right)
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

总结

强悍模拟 + 端点记录 + 区间范围合并大法