leetcode: 1562. Find latest grouping of size M [simulation + endpoint record + range merge]

分析

Build numberspoints
Each element represents the containing of the first position1the beginning and end of a continuous segment
Then each adding a new equivalent slave0变1,Consider merging with left and right
Might cut two reasonable chunks
as well as possibly adding a reasonable block
最后如果存在M的1块,can be included in the results
Finally update the two endpointsleft和right即可
Because the middle one cannot be used again~

ac code

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        # 模拟
        n = len(arr)
        # fuck[i]表示包含i在内的连续1left and right
        # [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

总结

Powerful Simulation + 端点记录 + Interval range merge Dafa