写在前面

上个周末的周赛题，自己写的时候就使用队列和递归模拟尝试了一下，时间复杂度O(n²)，不过超时了。自己平时对数据规模与复杂度的关系也不是很清楚，都是靠直觉，在想办法优化的时候犯了难，想要优化到O(n)，但是没想出来合适的解决办法，只能放弃。这里先记录一下正常情况下算法的时间复杂度与数据规模之间的关系。借用Santan's Death兄弟的博客

题目

核心思路

虽然题目很长而且有点晦涩难懂，不过只要按照题目给的示例自己模拟一遍就很容易理解题目的意思了，我就不在过多解释了。

直观模拟

直接暴力思想破解的话就是模拟他的过程，维护一个字符数组(初始状态全部填 '0')，然后根据 arr 数组的值依次更新数组中指定位置的字符，并且计算该步骤是否满足存在长度恰好为m的一组1(称为一次好操作)，遍历完成后最后一次好操作就是答案。
既然题目想要寻找的是最后一次好操作，那么我们可以逆序遍历，也就是相当于一串 '1' 按照 arr 数组的顺序变更为一串 '0'，此时只要找到第一次好操作返回即可。不过逆序遍历的平均复杂度并没有得到优化，若不存在好操作，还是会遍历所有的结果，所以核心的优化并不在这里。
而通过数据规模10^5可以知道算法的时间复杂度应该在 O(nlogn) 左右，而常见的优化方法就是二分查找，这道题给的标签也恰好是二分查找。由于逆序遍历的时候，每次循环只会更新一个先前存储过的区间 (假如原有一个子串'1111'，对应存储0 和 3，若接下来的步骤更新下标2，变为'1101'，在区间中插入一个1，更新为0 1 3) ，所以使用二分查找找到这个区间是可行的，不过我太菜了，没写出来。。。选择了使用一个TreeSet，从而满足查找的时间复杂度为 O(nlogn)。

模拟法代码

class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m == n)
            return n;

        TreeSet<Integer> set = new TreeSet<Integer>();
        // 相当于在最后一步骤形成的1串的左右各加一个0
        set.add(0);
        set.add(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            int index = arr[i];
            int low = set.lower(index);
            int high = set.higher(index);

            if (high - index - 1 == m || index - low - 1 == m) {
                return i;
            }
            set.add(index);
        }
        return -1;
    }
}

在最开始，现在set中加入 0 和 n + 1，这样可以保证操作一致，因为两边是0和一边是0、另一边是1的情况计算连续1串长度的方法是不一样的，所以相当于在串的两端各补了一个0。然后使用TreeSet中的lower()方法和higher()方法获取需要更新的区间的两端，然后判断、更新即可，代码比较简单，不过耗时350ms比较久。

类似链表的解法

由于求解的是每一个连续的'1'串长度，所以实际有用的下标就是首和尾，然后我们每次插入一个'1'的时候更新一下首尾指针，保证每一个'1'串开头位置的右指针指向结尾、结尾位置的左指针指向开头，并且维护一个cnt记录长度为m的'1'串的个数，每次操作都分别更新cnt变量，如果一次操作后cnt的值大于0，则代表这是一次好操作，然后保存最后一次好操作即可。

图解

可以想到，当插入'1'时，共有四种可能性：

• 插入位置左右两边都是0
• 插入位置左右两边都是1
• 插入位置左边是0右边是1
• 插入位置左边是1右边是0
  我们定义两个数组：l[i]表示i位置的左指针，r[i]表示i位置的右指针，并假设当前位置为x
  虽然图中例子只给了前两种情况，不过后两种情况与之类似，可以对照着写出指针更新过程，另外，由于每个位置都要考虑左右两边的字符的情况，所以可以在开头与结尾分别加一个0，保证操作的一致性。
  首先考虑可能一：左右两边都是0，这时候只要将插入位置的左右指针都指向自己即可。所以此时的操作应为：

  l[x] = r[x] = x

可能二：左右两边都是1(步骤四和步骤五的过程)，也就代表左边和右边均有'1'串，长度可能是任意的，假设两边长度都是1的情况(步骤四)，那么使左边元素的右指针指向右边元素，右边元素的左指针指向左边元素即可：

r[x - 1] = x + 1;
l[x + 1] = x - 1;

但是实际可能还有更长的串(步骤五)，左边长度为3，右边长度为1，根据图解，应该将最左边元素的右指针指向最右边的元素，最右边元素的左指针指向最左边元素，而根据步骤四，最左边元素可以通过x元素左边元素的左指针获得，同理最右边元素也可以根据x位置右边元素的右指针获得，于是我们可以得到这样的操作：

r[l[x - 1]] = r[x + 1];//l[x - 1]为左边串的最左端元素
l[r[x + 1]] = l[x - 1];//r[x + 1]为右边串的最右端元素

可能三与可能四与上边可能类似，就不再赘述了，还需要考虑的就是在更新左右指针的过程中怎么更新 cnt 变量。参考图解

• 可能一：左右都是0时，只有m = 1是要执行cnt++
• 可能二：左右都是1时，由于左右两边的串都有可能长度为m，此时连接之前应该将cnt--，而连接之后的串也可能出现长度为m的'1'串，所以连接之后若满足应cnt++
• 可能三与可能四：类似于可能二，分别考虑连接前串是否有长度为m，连接之后是否出现长度为m的串
  这样我们在最外层通过一次循环遍历arr数组，并对每个元素进行更新左右指针数组，并且判断本次是否为好操作即可。

完整代码

class Solution {
    private int[] l, r;// 当前位置的左右指针，0表示null

    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m == n)
            return n;

        l = new int[n + 2];
        r = new int[n + 2];
        int res = -1, cnt = 0;
        for (int i = 0; i < n; i++) {
            int x = arr[i];
            if (r[x + 1] != 0 && l[x - 1] != 0) {
                if (len(l[x - 1]) == m)
                    cnt--;
                if (len(x + 1) == m)
                    cnt--;
                r[l[x - 1]] = r[x + 1];
                l[r[x + 1]] = l[x - 1];
                if (len(l[x - 1]) == m)
                    cnt++;
            } else if (l[x - 1] != 0) {
                if (len(l[x - 1]) == m)
                    cnt--;
                l[x] = l[x - 1];
                r[l[x - 1]] = x;
                if (len(l[x - 1]) == m)
                    cnt++;
            } else if (r[x + 1] != 0) {
                if (len(x + 1) == m)
                    cnt--;
                r[x] = r[x + 1];
                l[r[x + 1]] = x;
                if (len(x) == m)
                    cnt++;
            } else {
                l[x] = r[x] = x;
                if (m == 1)
                    cnt++;
            }

            if (cnt > 0)
                res = i + 1;
        }
        return res;
    }

    /**
     * 计算左端为left的1串的长度
     * 
     * @param left
     * @return
     */
    public int len(int left) {
        return r[left] - left + 1;
    }
}

代码显得很长，不过实际上只是四种情况的分类讨论，理解了图解指针更新的过程，代码还是比较好懂的。

总结

第一种方法直观而且代码简洁，灵活的使用了TreeSet，不过时间效率比较低；第二种方法虽然代码也不是很长，但是这种思想不是很好想到，不过O(n)的时间复杂度还是很快的。自己对于数据结构的理解和运用还是不够熟练啊，另外这道题也让我了解了数据规模与目标算法时间复杂度的关系，收获颇丰。
文章中若有不正确的地方还请指出，感恩相遇~~