1562-查找大小为 M 的最新分组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个数组 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："00 **1** 00"，由 1 构成的组：["1"]
步骤 2："0010 **1** "，由 1 构成的组：["1", "1"]
步骤 3：" **1** 0101"，由 1 构成的组：["1", "1", "1"]
步骤 4："1 **1** 101"，由 1 构成的组：["111", "1"]
步骤 5："111 **1** 1"，由 1 构成的组：["11111"]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。

示例 2：

**输入：** arr = [3,1,5,4,2], m = 2
**输出：** -1
**解释：** 步骤 1："00 **1** 00"，由 1 构成的组：["1"]
步骤 2：" **1** 0100"，由 1 构成的组：["1", "1"]
步骤 3："1010 **1** "，由 1 构成的组：["1", "1", "1"]
步骤 4："101 **1** 1"，由 1 构成的组：["1", "111"]
步骤 5："1 **1** 111"，由 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

方法一：模拟

思路与算法

首先，我们考虑维护一个与原数组等大的数组 endpoints，其中 endpoints}[i] 表示数组中包含位置 i 的连续 1 的分组的起点和终点。如果 arr}[i] 为 0，则记起点和终点均为 -1。

例如，如果数组当前的取值为 [0, 1, 1, 1, 0, 1, 1]，则数组 endpoints 的取值为：

[(-1, -1), (2, 4), (2, 4), (2, 4), (-1, -1), (6, 7), (6,7)]

注意本题中数组下标是从 1 开始的。

起始时，数组 arr 的值都为 0。随后当进行每一步操作时，如果该步骤为将 arr}[i] 的值设为 1，则有以下三种情况：

  • 如果 arr}[i] 的左右两个相邻元素（如果有）的值均为 -1，则此时生成了一个新的长度为 1 的分组；
  • 如果左右两个相邻元素（如果有）的之一的取值为 1，则此时会生成一个新的分组，该分组取代了已有的某个分组，其长度为该已有分组的长度加 1；
  • 如果左右两个相邻元素的取值都为 1，则此时会将左右两个分组合并成一个新的分组，新分组的长度为两个分组的长度之和再加上 1。同时，原本的两个分组会随之消失。

在每种情况下，我们都会修改数组 endpoints。不过对于一个新生成的分组，我们无需修改其中每个位置的取值：只需修改该分组左右端点处的取值即可。这是因为，在进行每一步操作时，都不会在一个已有的分组内部做修改，只会考虑已有分组的端点处的取值。

与此同时，我们也需要统计长度为 m 的分组数量。如果进行完第 i 次操作后，长度为 m 的分组数量大于 0，则更新返回值为 i。遍历结束后，就能得到答案。

代码

[sol1-C++]
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
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        vector<pair<int, int>> endpoints(n + 1, make_pair(-1, -1));
        int cnt = 0;
        int ret = -1;

        for (int i = 0; i < n; i++) {
            int left = arr[i], right = arr[i];
            if (arr[i] > 1 && endpoints[arr[i] - 1].first != -1) {
                left = endpoints[arr[i] - 1].first;
                int leftLength = endpoints[arr[i] - 1].second - endpoints[arr[i] - 1].first + 1;
                if (leftLength == m) {
                    cnt--;
                }
            }
            if (arr[i] < n && endpoints[arr[i] + 1].second != -1) {
                right = endpoints[arr[i] + 1].second;
                int rightLength = endpoints[arr[i] + 1].second - endpoints[arr[i] + 1].first + 1;
                if (rightLength == m) {
                    cnt--;
                }
            }
            int length = right - left + 1;
            if (length == m) {
                cnt++;
            }
            if (cnt > 0) {
                ret = i + 1;
            }
            endpoints[left] = endpoints[right] = make_pair(left, right);
        }
        return ret;
    }
};
[sol1-Java]
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
39
class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        int[][] endpoints = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(endpoints[i], -1);
        }
        int cnt = 0;
        int ret = -1;

        for (int i = 0; i < n; i++) {
            int left = arr[i], right = arr[i];
            if (arr[i] > 1 && endpoints[arr[i] - 1][0] != -1) {
                left = endpoints[arr[i] - 1][0];
                int leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1;
                if (leftLength == m) {
                    cnt--;
                }
            }
            if (arr[i] < n && endpoints[arr[i] + 1][1] != -1) {
                right = endpoints[arr[i] + 1][1];
                int rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1;
                if (rightLength == m) {
                    cnt--;
                }
            }
            int length = right - left + 1;
            if (length == m) {
                cnt++;
            }
            if (cnt > 0) {
                ret = i + 1;
            }
            endpoints[left][0] = endpoints[right][0] = left;
            endpoints[left][1] = endpoints[right][1] = right;
        }
        return ret;
    }
}
[sol1-Python3]
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
class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        endpoints = [(-1, -1) for _ in range(n + 1)]
        cnt = 0
        ret = -1

        for i in range(n):
            left = right = arr[i]
            if arr[i] > 1 and endpoints[arr[i] - 1][0] != -1:
                left = endpoints[arr[i] - 1][0]
                leftLength = endpoints[arr[i] - 1][1] - endpoints[arr[i] - 1][0] + 1;
                if leftLength == m:
                    cnt -= 1
            if arr[i] < n and endpoints[arr[i] + 1][1] != -1:
                right = endpoints[arr[i] + 1][1]
                rightLength = endpoints[arr[i] + 1][1] - endpoints[arr[i] + 1][0] + 1;
                if rightLength == m:
                    cnt -= 1
            
            length = right - left + 1
            if length == m:
                cnt += 1
            if cnt > 0:
                ret = i + 1
            endpoints[left] = endpoints[right] = (left, right)

        return ret

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。在处理每个步骤的时候，我们仅访问了左右两个相邻元素的取值，也仅修改了新分组左右端点处的取值，因此每个步骤的耗时都是 O(1) 的。

  • 空间复杂度：O(n)。我们需要开辟一个与原数组长度相同的数组 endpoints。

 Comments
On this page
1562-查找大小为 M 的最新分组