ORID39 biweekly contest sliding

今天参加了biweekly & weekly contest。

[1493] Longest Subarray of 1's After Deleting One Element

算法

用什么算法？
这道题我觉得是要用sliding window的方法来做，但是我不知道如何implement。结果做了半天没做出来
sliding window 主要有几个部分

1. 一个for loop 来过一遍这个list 里面的每个element。
2. 通常这个for loop的指针就是sliding window 的结尾
3. 在新建一个sliding window 指针开始的参数，一般就可以叫windowStart. 通常也是为0
4. 根据题目要求不断增加i/windowstart（因为你要确保的就是返回最大的interval，这时候如果你sliding window里面有个数违反了题目的要求，那你就需要增加i，也就是shrink your window size。）
5. 返回最长或者最短的window size。

代码实现

    public static int longestSubarray(int[] A) {
        int windowStart = 0, windowEnd, maxZero = 1, result = 0;
        for (windowEnd = 0; windowEnd < A.length; windowEnd++) {
            if (A[windowEnd] == 0) maxZero--;
            while (maxZero < 0) {
                if (A[windowStart] == 0) {
                    maxZero++;
                }
                windowStart++;
            }
            result = Math.max(result, windowEnd - windowStart);
        }
        return result;
    }

这段是我通过这个视频介绍的方式写出这道题的解法，根lee215的方法差不多，其实他就是把命名方法简化了，他的windowEnd 就是j，他的windowstart就是i，他的k就是我的maxZero，这里代表这个列表里最多有几个0，下面是lee215 的解法

    public int longestSubarray(int[] A) {
        int i = 0, j, k = 1, res = 0;
        for (j = 0; j < A.length; ++j) {
            if (A[j] == 0) {
                k--;
            }
            while (k < 0) {
                if (A[i] == 0) {
                    k++;
                }
                i++;
            }
            res = Math.max(res, j - i);
        }
        return res;
    }

我一开始没看懂，后来结合着那个视频去看发现还是挺好理解的。
最主要还是你要看出来这道题可以用sliding window去解决。
其实题目里问到了最长subarray，基本上可以确定用sliding window了。最长或者最短subarray基本上可以用sliding window解决。