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

思路

官方思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
首先，我们考虑维护一个与原数组等大的数组 \textit{endpoints}endpoints，其中 \textit{endpoints}[i]endpoints[i] 表示数组中包含位置 ii 的连续 11 的分组的起点和终点。如果 \textit{arr}[i]arr[i] 为 00，则记起点和终点均为 -1−1。

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

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

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

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

如果 \textit{arr}[i]arr[i] 的左右两个相邻元素（如果有）的值均为 -1−1，则此时生成了一个新的长度为 11 的分组；
如果左右两个相邻元素（如果有）的之一的取值为 11，则此时会生成一个新的分组，该分组取代了已有的某个分组，其长度为该已有分组的长度加 11；
如果左右两个相邻元素的取值都为 11，则此时会将左右两个分组合并成一个新的分组，新分组的长度为两个分组的长度之和再加上 11。同时，原本的两个分组会随之消失。
在每种情况下，我们都会修改数组 \textit{endpoints}endpoints。不过对于一个新生成的分组，我们无需修改其中每个位置的取值：只需修改该分组左右端点处的取值即可。这是因为，在进行每一步操作时，都不会在一个已有的分组内部做修改，只会考虑已有分组的端点处的取值。

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-latest-group-of-size-m/solution/cha-zhao-da-xiao-wei-m-de-zui-xin-fen-zu-by-leetco/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

按理来说，树状数组和dp能做的，但我用不来。
最后通过108/114，状态欠佳了。

代码

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
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n=arr.size();
        vector<pair<int,int>> endpoint(n+1,make_pair(-1,-1));
        int cnt=0;
        int res=-1;
        int left,right;
        for(int i=0;i<n;i++){
            left=arr[i],right=arr[i];
            if(arr[i]>1&&endpoint[arr[i]-1].first!=-1){
                left=endpoint[arr[i]-1].first;
                int leftLength=endpoint[arr[i]-1].second-endpoint[arr[i]-1].first+1;
                if(leftLength==m){
                    cnt--;
                }
            }
            if(arr[i]<n&&endpoint[arr[i]+1].second!=-1){
                right=endpoint[arr[i]+1].second;
                int rightLength=endpoint[arr[i]+1].second-endpoint[arr[i]+1].first+1;
                if(rightLength==m){
                    cnt--;
                }
            }
            if(right-left+1==m)
                cnt++;
            if(cnt>0)
                res=i+1;
            endpoint[left]=endpoint[right]=make_pair(left,right);
        }
        return res;
    }
};

参考

  1. https://leetcode-cn.com/problems/find-latest-group-of-size-m/ ↩
  2. https://leetcode-cn.com/problems/find-latest-group-of-size-m/solution/cha-zhao-da-xiao-wei-m-de-zui-xin-fen-zu-by-leetco/ ↩