算法leetcode

【多解法】力扣1562-查找大小为M的最新分组

字数统计: 3k字   |   阅读时长: 14分
, , , , ,

摘要: 一题多解的标杆

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个有很多解法的问题，涉及到非常多知识点：

  • 算法1: 区间合并
  • 算法2: 并查集
  • 算法3: 逆向思维 + 平衡树
  • 算法4: 逆向思维 + 减治
  • 算法5: 滑动窗口 + 单调队列

$1 题目

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

给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。

在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。

给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。

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

提示：

1
2
3
4
5
n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
arr 中的所有整数 互不相同
1 <= m <= arr.length

示例 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

$2 题解

算法1: 区间合并

枚举 i，对应的数值是 arr[i]，对应的操作是将 s[arr[i]] 置 1。

s[arr[i]] 置 1 之后可能面对三种情况

1
2
3
4
5
6
7
8
9
10
两个条件
(1) arr[i]+1 <= n && s[arr[i]+1] 已经更新过
(2) arr[i]-1 >= 1 && s[arr[i]-1] 已经更新过

1. (1)(2) 均符合
    arr[i] 对应的新段的长度为相邻两段长度+1, arr[i]+1 和 arr[i]-1 对应的两段删掉
2. (1)(2) 符合其中一个
    arr[i] 对应的新段的长度为相邻的那一段的长度+1, arr[i]+1 或 arr[i]-1 对应的那一段删掉
3. (1)(2) 均不符合
    arr[i] 对应的新段长度为 1，无需删原有段

在枚举过程中，始终维护一个变量 cnt_m，表示长度为 m 的段的个数，当新增段长度为 m 时 ++cnt_m，当删除段的长度为 m 时，--cnt_m

枚举过程中维护一个 arr[i] 对应的段的断点信息的数组 vector<Range> ranges，ranges[arr[i]] 记录 arr[i] 对应的段的左右端点信息。

1
arr[i] 对应的段： [ranges[arr[i]].l, ranges[arr[i]]r]

当 arr[i] 在端点的时候，信息要正确，用于给相邻点更新信息。而当 arr[i] 不在端点的时候，可以不在更新了，因为不会再有相邻点依赖它更新信息，因此无需再为其正确性负责。

代码 (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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        vector<Range> range(n + 1);
        int cnt_m = 0;
        int ans = -1;
        for(int i = 0; i < n; ++i)
        {
            int val = arr[i];
            int len_val;
            if((val < n && range[val + 1].l != -1) && (val > 1 && range[val - 1].l != -1))
            {
                range[range[val - 1].l].r = range[val + 1].r;
                range[range[val + 1].r].l = range[val - 1].l;
                len_val = range[val + 1].r - range[val - 1].l + 1;
                if(range[val + 1].r - val == m)
                    --cnt_m;
                if(val - range[val - 1].l == m)
                    --cnt_m;
            }
            else if(val < n && range[val + 1].l != -1)
            {
                range[range[val + 1].r].l = val;
                range[val].r = range[val + 1].r;
                range[val].l = val;
                len_val = range[val + 1].r - val + 1;
                if(range[val + 1].r - val == m)
                    --cnt_m;
            }
            else if(val > 1 && range[val - 1].l != -1)
            {
                range[range[val - 1].l].r = val;
                range[val].l = range[val - 1].l;
                range[val].r = val;
                len_val = val - range[val - 1].l + 1;
                if(val - range[val - 1].l == m)
                    --cnt_m;
            }
            else
            {
                range[val].l = val;
                range[val].r = val;
                len_val = 1;
            }
            if(len_val == m)
                ++cnt_m;
            if(cnt_m > 0)
                ans = i + 1;
        }
        return ans;
    }

private:
    struct Range
    {
        int l, r;
        Range(int l, int r):l(l),r(r){}
        Range():l(-1),r(-1){}
    };
};

优化

可以压缩一些信息，不用 vector<Range> 保存每个点对应的区间信息，只用 vector<int> lens 保存每个点对应的区间长度信息即可。

可以将 lens 两侧扩展一个单位，避免边界处理

同样用 cnt_m 维护长 m 区间个数

1
2
3
4
5
6
7
8
9
10
11
vector<int> lens(n + 2, 0) 
枚举 i，对应值 val = arr[i]，此时 lens[val] = 0
if(len[val - 1] == m)
    --cnt_m;
if(len[val + 1] == m)
    --cnt_m;
lens[val] = len[val - 1] + len[val + 1] + 1
lens[val + lens[val + 1]] = lens[val]
lens[val - lens[val - 1]] = lens[val]
if(lens[val] == m)
    ++cnt_m;

代码 (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
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        vector<int> lens(n + 2);
        int cnt_m = 0;
        int ans = -1;
        for(int i = 0; i < n; ++i)
        {
            int val = arr[i];
            if(lens[val - 1] == m)
                --cnt_m;
            if(lens[val + 1] == m)
                --cnt_m;
            lens[val] = lens[val - 1] + lens[val + 1] + 1;
            if(lens[val] == m)
                ++cnt_m;
            if(cnt_m > 0)
                ans = i + 1;
            lens[val + lens[val + 1]] = lens[val];
            lens[val - lens[val - 1]] = lens[val];
        }
        return ans;
    }
};

算法2: 并查集

用并查集维护区间合并，并查集中增加一个集合级的权，表示区间长度。初始时，权均为 0。

每一个 s[arr[i]] 置 1 时，查询并查集中 arr[i] + 1 和 arr[i] - 1 的权，若为 0，则该点尚未置 1，否则在并查集中合并这两个元素。

并查集中维护一个变量 cnt_m 表示权为 m 的集合个数。

代码 (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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        // 维护 [1..n]
        _father.assign(n + 1, 0);
        _rank.assign(n + 1, 0);
        _weight.assign(n + 1, 0);
        for(int i = 1; i <= n; ++i)
            _father[i] = i;
    }

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y)
            return;

        if(_rank[x] < _rank[y])
        {
            _father[x] = y;
            _weight[y] += _weight[x];
        }
        else
        {
            _father[y] = x;
            _weight[x] += _weight[y];
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

    void set(int x)
    {
        _weight[x] = 1;
    }

    int get(int x)
    {
        return _weight[_find(x)];
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<int> _weight;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        UnionFindSet unionfindset(n);
        int ans = -1;
        int cnt_m = 0;
        for(int i = 0; i < n; ++i)
        {
            int val = arr[i];
            unionfindset.set(val);
            if(val > 1)
            {
                int len_left = unionfindset.get(val - 1);
                if(len_left > 0)
                {
                    if(len_left == m)
                        --cnt_m;
                    unionfindset.merge(val, val - 1);
                }
            }
            if(val < n)
            {
                int len_right = unionfindset.get(val + 1);
                if(len_right > 0)
                {
                    if(len_right == m)
                        --cnt_m;
                    unionfindset.merge(val, val + 1);
                }
            }
            int val_len = unionfindset.get(val);
            if(val_len == m)
                ++cnt_m;
            if(cnt_m > 0)
                ans = i + 1;
        }
        return ans;
    }
};

算法3: 逆向思维 + 平衡树

正向思维

全 0 串通过正向操作变为全 1 串。

求最后一次出现的长度刚好为 m 的全 1 串。

逆向思维

全 1 串通过反向操作变为全 0 串。

求第一次出现的长度刚好为 m 的全 1 串。

用平衡树维护区间 map<int, int> ranges，键为左端点，值为右端点，初始时 ranges 中只有一个区间 [1, n]。

若 n == m，直接返回 n。

按照 i = n - 1, …, 0 的顺序枚举 arr[i]，找到 arr[i] 的所属区间 it = ranges.lower_bound(arr[i])，
有 it -> first <= arr[i] <= it -> second，区间更新过程：

1
2
3
4
5
6
7
记录 it 所属区间 [l, r] = [it -> first, it -> second]
删除 it 所属区间 it = ranges.erase(it)
插入新区间:
    若 arr[i] - 1 >= l, 插入 [l, arr[i] - 1]
    若 arr[i] + 1 <= r, 插入 [arr[i] + 1, r]
    插入前判断区间长度是否等于 m
    若等于 m，返回 i + 1

代码 (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
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        if(n == m) return n;
        // m < n
        map<int, int> ranges;
        ranges[1] = n;
        for(int i = n - 1; i >= 0; --i)
        {
            int val = arr[i];
            auto it = prev(ranges.upper_bound(val));
            int l = it -> first;
            int r = it -> second;
            ranges.erase(it);
            if(val - 1 >= l)
            {
                if(val - l == m)
                    return i;
                ranges[l] = val - 1;
            }
            if(val + 1 <= r)
            {
                if(r - val == m)
                    return i;
                ranges[val + 1] = r;
            }
        }
        return -1;
    }
};

算法4: 逆向思维 + 减治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
待求解问题
int solve(const vector<int>& arr, int idx, int l, int r, const int m)
返回 s[l..r] 上首次出现长 m 全 1 串的时间

问题直接可解的情况
(1) [l, r] 长度刚好为 m，返回 0
if(r - l + 1 == m)
    return 0;
(2) l > r 以及 r - l + 1 均无解，返回 -1
if(l > r || r - l + 1 < m)
    return -1;

arr[idx] 是当前迭代的 arr 上的值，采用逆向思维, idx 从 n - 1 往 0 迭代

子问题分割点 arr[idx]
(1) arr[idx] 在区间 [l, r] 外，在 [l, r] 上迭代 arr[idx - 1]
(2) arr[idx] 在 [l, r] 内，可以分割子问题:
    在 [l, arr[idx] - 1] 和 [arr[idx] + 1, r] 上分别迭代 arr[idx - 1]
    然后合并左右的结果

代码 (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
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        int ans = solve(arr, n - 1, 1, n, m);
        return ans == -1 ? -1 : n - ans;
    }

private:
    int solve(const vector<int>& arr, int idx, int l, int r, const int m)
    {
        if(r - l + 1 == m)
            return 0;
        if(l > r || r - l + 1 < m)
            return -1;
        if(arr[idx] < l || arr[idx] > r)
        {
            int ans = solve(arr, idx - 1, l, r, m);
            return ans == -1 ? -1 : 1 + ans;
        }
        int left = solve(arr, idx - 1, l, arr[idx] - 1, m);
        int right = solve(arr, idx - 1, arr[idx] + 1, r, m);
        if(right == -1 && left == -1)
            return -1;
        else if(left == -1)
            return right + 1;
        else if(right == -1)
            return left + 1;
        else
            return min(left, right) + 1;
    }
};

算法5: 滑动窗口

转换为滑动窗口最大值问题，用滑动窗口+单调队列解决。

arr[i] 的含义是在 i 时间操作 arr[i] 位置，将对应关系反过来形成一个 vec[arr[i]] = i 表示位置 arr[i] 在 i 时间操作。

arr 与 vec 的对应关系在本题条件下是一一对应的。

单独考虑 vec，vec[i] 表示 s[i] 这个位置从 0 变为 1 的时间。

长度恰好为 m 的连续 1 构成的序列相当于 vec 上一段长度为 m 的窗口 [i, i + m - 1]，其窗口最大值小于窗口两边相邻的值 vec[i - 1] 和 vec[i + m]，即窗口两侧从 0 变成 1 的时间均比窗口的最晚时间还晚。

代码 (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
class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size();
        if(n == m) return n;
        // vec[0, 1, ..., n, n + 1]
        vector<int> vec(n + 2, n + 1);
        for(int i = 0; i < n; ++i)
            vec[arr[i]] = i + 1;
        deque<int> deq;
        int ans = -1;
        // 将 deq 中预处理好 vec[1..m-1] 这个长 m-1 的窗口
        for(int i = 1; i < m; ++i)
        {
            while(!deq.empty() && vec[deq.back()] <= vec[i])
                deq.pop_back();
            deq.push_back(i);
        }
        for(int i = m; i < n + 1; ++i)
        {
            while(!deq.empty() && vec[deq.back()] <= vec[i])
                deq.pop_back();
            deq.push_back(i);
            // 此时 deq 中是 [i-m+1..i] 的信息
            int min_neighbor = min(vec[i + 1], vec[i - m]);
            if(vec[deq.front()] < min_neighbor)
                ans = max(ans, min_neighbor - 1);
            // 迭代下一个 i 之前，将窗口调整为 [i-m+2, i]
            if(deq.front() == i - m + 1)
                deq.pop_front();
        }
        return ans;
    }
};
Share