Medium

题目描述

给你一个数组 arr，该数组表示从 1 到 n 的数字的排列。

你有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0。在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位置 arr[i] 的位设置为 1。

你还被给定一个整数 m。请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由若干个 1 组成的子字符串，且不能向任一方向扩展。

返回存在长度恰好为 m 的一组 1 的最后步骤。如果不存在这样的组，请返回 -1。

示例 1：

输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1："00100"，分组：["1"]
步骤 2："00101"，分组：["1", "1"]
步骤 3："10101"，分组：["1", "1", "1"]
步骤 4："11101"，分组：["111", "1"]
步骤 5："11111"，分组：["11111"]
存在长度为 1 的分组的最后步骤是步骤 4。

示例 2：

输入：arr = [3,1,5,4,2], m = 2
输出：-1
解释：
步骤 1："00100"，分组：["1"]
步骤 2："10100"，分组：["1", "1"]
步骤 3："10101"，分组：["1", "1", "1"]
步骤 4："10111"，分组：["1", "111"]
步骤 5："11111"，分组：["11111"]
在任何步骤中都不存在长度为 2 的分组。

约束条件：

  • n == arr.length
  • 1 <= m <= n <= 10^5
  • 1 <= arr[i] <= n
  • arr 中的所有整数都不相同。

解题思路

这道题可以通过两种思路来解决：

方法一：正向模拟 从前往后遍历数组，维护连续的1的分组信息。每次添加一个1时，需要检查是否与相邻的分组合并。使用哈希表记录每个分组长度的数量，当长度为m的分组数量大于0时更新答案。

方法二：反向思考（推荐） 从后往前遍历数组，相当于从全1的状态开始，逐步移除某些位置的1。这样问题转化为：移除一个1后，原来的一个长分组会分裂成两个分组。使用并查集或区间映射来维护分组信息。

具体实现中，我们可以使用哈希表记录每个长度分组的数量。对于反向思考的方法：

  1. 从最后一步开始，逐步"撤销"设置1的操作
  2. 每次撤销时，一个长分组会分裂成两个短分组
  3. 维护长度为m的分组数量，当数量>0时更新答案

这种方法的优势是避免了复杂的区间合并逻辑，而是通过分裂来简化处理过程。

代码实现

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        if (m == n) return n;
        
        vector<int> lengths(n + 2, 0);
        vector<int> count(n + 1, 0);
        count[n] = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            int pos = arr[i];
            int left = lengths[pos - 1];
            int right = lengths[pos + 1];
            
            count[left + right + 1]--;
            if (count[m] > 0) return i;
            
            count[left]++;
            count[right]++;
            
            lengths[pos - left] = left;
            lengths[pos + right] = right;
        }
        
        return -1;
    }
};

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        if m == n:
            return n
        
        lengths = [0] * (n + 2)
        count = [0] * (n + 1)
        count[n] = 1
        
        for i in range(n - 1, -1, -1):
            pos = arr[i]
            left = lengths[pos - 1]
            right = lengths[pos + 1]
            
            count[left + right + 1] -= 1
            if count[m] > 0:
                return i
            
            count[left] += 1
            count[right] += 1
            
            lengths[pos - left] = left
            lengths[pos + right] = right
        
        return -1

public class Solution {
    public int FindLatestStep(int[] arr, int m) {
        int n = arr.Length;
        if (m == n) return n;
        
        int[] lengths = new int[n + 2];
        int[] count = new int[n + 1];
        count[n] = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            int pos = arr[i];
            int left = lengths[pos - 1];
            int right = lengths[pos + 1];
            
            count[left + right + 1]--;
            if (count[m] > 0) return i;
            
            count[left]++;
            count[right]++;
            
            lengths[pos - left] = left;
            lengths[pos + right] = right;
        }
        
        return -1;
    }
}

/**
 * @param {number[]} arr
 * @param {number} m
 * @return {number}
 */
var findLatestStep = function(arr, m) {
    const n = arr.length;
    const lengths = new Array(n + 2).fill(0);
    const count = new Array(n + 1).fill(0);
    let result = -1;
    
    for (let i = 0; i < n; i++) {
        const pos = arr[i];
        const leftLen = lengths[pos - 1];
        const rightLen = lengths[pos + 1];
        const newLen = leftLen + rightLen + 1;
        
        lengths[pos - leftLen] = newLen;
        lengths[pos + rightLen] = newLen;
        
        count[leftLen]--;
        count[rightLen]--;
        count[newLen]++;
        
        if (count[m] > 0) {
            result = i + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)