题目内容

给你一个数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-latest-group-of-size-m
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这个题目我是在二分练习中看到的，当时对二分是真的完全没有思路，不过可能真的就是一下子来灵感了，感觉可以用单调栈来实现这个题目。

而且单调栈的实现效果还可以！
首先我来说一下单调栈的原理，主要就是下面这个图的意思，圈里的就是最近的大于他的位置的宽度：

上图对应的样例为：
[10,6,9,4,7,8,5,2,1,3]
1

我们已经知道了每一次操作会将哪一个位置置1，那么我们自然可以根据这个信息，反过来理解，也就是第arr[i]个位置会在第i次操作的时候被置1，既然如此，我们就可以通过单调栈，对于每一个位置，来看我们刚好把这个元素置1的时候，他所在的位置的会有几个连续的1.如果这个位置对应的连续的1的个数刚好满足要求，我们就要看左右两边比这个位置要晚被置1的数是第几次操作，我们就可以坚持到左右两边中较小的操作轮次-1的时候依旧满足要求。

众所周知，单调栈最后经常出现那种最右边单调，然后不出栈的情况，所以我这里也是直接左右都放了两个最大值，确保能把有意义的数据都排挤出来，确保答案的正确性。

不过该说不说的，这次我是真的感觉到了刷题的进步了，这个问题能联想到单调栈我是真的理解了为什么老师总是会说灵感，感觉是要连出来的，这个我真感觉挺灵性的，我第一次在做OJ题的时候这么为我自己感觉骄傲，且容我插会腰（doge）。

代码实现

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int a[100009]={0};
        for(int i=0;i<arr.size();i++){
            a[arr[i]]=i+1;
        }
        a[0]=INT_MAX;
        a[arr.size()+1]=INT_MAX;
        stack<int> zhan;
        int ans=-1;
        for(int i=0;i<arr.size()+2;i++){
            if(zhan.empty()){
                zhan.push(i);
            }
            else{
                if(a[i]<a[zhan.top()]){
                    zhan.push(i);
                }
                else{
                    while(a[zhan.top()]<a[i]){
                        int shu=zhan.top();zhan.pop();
                        // cout<
                        
                        int cha=i-zhan.top()-1;
                        if(cha==m){
                            // cout<
                            if(zhan.top()==0&&i==arr.size()+1){
                                ans=arr.size();
                                continue;
                            }
                            else if(zhan.top()==0){
                                ans=ans>a[i]-1?ans:a[i]-1;
                                continue;
                            }
                            else if(i==arr.size()+1){
                                ans=ans>a[zhan.top()]-1?ans:a[zhan.top()]-1;
                                continue;
                            }
                            else{
                                ans=ans>(a[zhan.top()]<a[i]?a[zhan.top()]-1:a[i]-1)?ans:(a[zhan.top()]<a[i]?a[zhan.top()]-1:a[i]-1);
                            }
                        }
                    }
                    zhan.push(i);
                }
            }
        }
        // cout<
        return ans;
    }
};

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