原文链接: https://leetcode-cn.com/problems/find-latest-group-of-size-m

英文原文

Given an array arr that represents a permutation of numbers from 1 to n.

You have a binary string of size n that initially has all its bits set to zero. At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1.

You are also given an integer m. Find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1's such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.

 

Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

Example 3:

Input: arr = [1], m = 1
Output: 1

Example 4:

Input: arr = [2,1], m = 2
Output: 2

 

Constraints:

• n == arr.length
• 1 <= m <= n <= 105
• 1 <= arr[i] <= n
• All integers in arr are distinct.

中文题目

给你一个数组 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.length
• 1 <= n <= 10^5
• 1 <= arr[i] <= n
• arr 中的所有整数 互不相同
• 1 <= m <= arr.length

通过代码

高赞题解

解题思路：

每操作一次，新增的 1 可能会有如下三种情况：

• 左右都是 0。此时该位置作为 新增段独立存在。
• 仅有左边或者右边。此时该位置 会将某个旧段的长度加 1。
• 左右都是 1。此时 该位置会将两个旧段合并成一个新段。

我们现在维护一个字典 M，M 的 key 表示段的长度，value 表示在字符串中，长度为 key 的段的数量。初始时，M 中无记录。接下来，让我们看下上述三种情况分别对 M 造成了哪些变化。

• 情况一：新增了一个长度为 1 的段。M[1] += 1。
• 情况二：删除一个长度为 L 的段，增加一个长度为 L+1的段。M[L] -= 1；M[L+1] += 1；
• 情况三：删除两个长度分别为 X，Y 的段，增加一个长度为 X+Y+1 的段。
  M[X] -= 1；M[Y] -= 1；M[X+Y+1] += 1；

然后记录一下 最后一次使 M[m] 不为零的操作 即可。

另外，还有一个重要问题，如何确定被删除段的长度呢？

设有一个数组 link，当 arr[i] 为某个段的端点时，link[i] 才有意义，其值代表另一个端点的位置。

接下来，上述三种情况如何更新 link。

• 情况一：因为长度为 1，所以 link[i] = i；

• 情况二：加入新增点成为某个旧段的右端点；
  则被删段长度为 (i-1) - link[i-1] + 1；link[link[i-1]] = i，link[i] = link[i-1]。
  为左端点时同理，机智的老铁们可自行推导。
  

• 情况三：左删除段长度为：(i-1) - link[i-1] + 1；
  有删除段长度为：link(i+1) - (i+1) + 1；
  更新：link[link[i-1]], link[link[i+1]] = link[i+1], link[i-1]。
  

另外，实现时根本不需要 M，因为我们只关心长度为 m 的段的数量~。

[]
int link[100001] = {0};

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int cnt = 0;
        memset(link, -1, sizeof(link));
        int anw = -1;
        for(int i = 0; i < arr.size(); i++) {
            int pos = arr[i] - 1;
            link[pos] = pos;
            int L = pos, R = pos;
            if(0 < pos && link[pos-1] != -1) {
                if(pos-1 - link[pos-1] + 1 == m) {
                    cnt--;
                }
                L = link[pos-1];
            }
            if(pos+1 < arr.size() && link[pos+1] != -1) {
                if(link[pos+1] - (pos+1) + 1 == m) {
                    cnt--;
                }
                R = link[pos+1];
            }
            
            link[L] = R;
            link[R] = L;
            
            if(R-L+1 == m) {
                cnt++;
            }
            if(cnt > 0) {
                anw = i+1;
            }
        }
        return anw;
    }
};

统计信息

通过次数	提交次数	AC比率
4323	13932	31.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言