[LeetCode]-滑动窗口

前言

记录刷 LeetCode 时遇到的滑动窗口相关题目

209.长度最小的子数组

滑动窗口不适合含负值的数组

/** *劣质的 滑动窗口 ，由于把考虑到的特殊情况都用if-else单独拎出来处理，导致过多的if-else分支，一方面代码不够简洁，一方面执行效率也降低了 * =============下面做了四个改进=============================== * ==========改进过程可以明显发现影响时间最大的就是count函数======================================================== * ====由于滑动窗口是O(n)算法且是一个元素一个元素进行操作，所以用变量维护的方法维护每一个滑动窗口(子数组)的和是可取的，======= * ====完全不需要每次都调用循环的方法去求和================================================================= * =================================================================================================== **/
public int minSubArrayLen(int target, int[] nums) {
    
    int length = nums.length;
    /* 改进一： 首先这两个if-else是完全没必要的 if(length == 0){ return 0; } if(length == 1){ return nums[0] >= target ? 1 : 0; }*/
    int result = length + 1;
    int left = 0;
    int right = 0;
    /*改进二： * 这段是用来初始化窗口的，改掉这一段后,时间明显提升，可能是因为每一次都调用了count方法，而count方法本身是个循环，应该用变量维护的方法求 * 当前子数组的和而不是每次变换窗口都计算子数组的和 * while (right < length && count(nums, left, right) < target){ * right++; *}*/
    int count1 = 0;
    while (right < length){
    
        count1 += nums[right];
        if(count1 >= target){
    
            break;
        }else {
    
            right++;
        }
    }
    /* 注意点1 * 此时right可能已经超出数组长度了· 即特例 ：所有数组元素加起来都不等于target，也就是说 result 可能是没有被修改的， * 所以最后不应该直接返回result，而是返回 result == length + 1 ? 0 : result*/
    while (right < length){
    
        if(count1 >= target){
    
            result = Math.min(right - left + 1, result);
            /*改进三：就算left加一后与right重合了也无所谓，此时子数组和为0，到下一次循环时right会加一，不用担心left比right大的 if(left + 1 <= right) { count1 -= nums[left]; left++; }else { right++; left++; if(right < length){ count1 = nums[left]; } }*/
            count1 -= nums[left++];
        }else {
    
            right++;
            if(right < length){
    
                count1 += nums[right];
            }
        }
    }
    /* 注意点2 当所有数组元素加起来都不等于target时应返回0*/
    return result == length + 1 ? 0 : result;
}
/*public int count(int[] nums, int left, int right){ if(left == right){ return nums[left]; } int count = 0; for(int i = left;i <= right && i < nums.length;i++){ count += nums[i]; } return count; }*/
//整理后是：
public int minSubArrayLen(int target, int[] nums) {
    
    int length = nums.length;
    int result = length + 1;
    int left = 0;
    int right = 0;
    int count1 = 0;
    while (right < length){
    
        count1 += nums[right];
        if(count1 >= target){
    
            break;
        }else {
    
            right++;
        }
    }
    while (right < length){
    
        if(count1 >= target){
    
            result = Math.min(right - left + 1, result);
            count1 -= nums[left++];
        }else {
    
            right++;
            if(right < length){
    
                count1 += nums[right];
            }
        }
    }
    return result == length + 1 ? 0 : result;
}

904.水果成篮

public int totalFruit(int[] fruits) {
    
    int length = fruits.length;
    /* 不必要的特判： if(length == 1){ return 1; } if(length == 2){ return 2; }*/
    int left = 0;
    int right = -1;
    //找到与首元素不同的元素,对应情况：前面好几个都一样
    for(int i = 1;i < length;i++){
    
        if(fruits[i] != fruits[left]){
    
            right = i;
            break;
        }
    }
    //特例 ： 所有数都是同一个
    if(right == -1){
    
        return length;
    }
    int record1;
    int record2;
    int maxCount = right - left + 1;
    while (right < length - 1){
    
        //更新记录的两个数 
        record1 = fruits[left];
        record2 = fruits[right];
        while (right < length - 1 && (fruits[right + 1] == record1 || fruits[right + 1] == record2)){
    
            right++;
        }
        maxCount = Math.max(maxCount, (right - left + 1));
        int temp = right;
        while (fruits[temp] == fruits[right]){
    
            temp--;
        }
        left = temp + 1;
        //此时要么right的下一个是不同的数，要么right >= length - 1然后跳出循环，所以right++是完全买毛病的
        right++;
    }
    return maxCount;
}

76.最小覆盖子串(hard)

class Solution {
    
    private Map<Character,Integer> tMap = new HashMap<>();
    private Map<Character,Integer> resMap = new HashMap<>();
    public String minWindow(String s, String t) {
    
        if(s.length() == 0){
    
            return "";
        }
        int tLength = t.length();
        int sLength = s.length();
        for (int i = 0; i < tLength; i++) {
    
            char c = t.charAt(i);
            tMap.put(c,tMap.getOrDefault(c,0) + 1);
        }
        int l = 0;
        while (l < sLength && !tMap.containsKey(s.charAt(l))){
    
            l++;
        }
        int r = sLength - 1;
        while (r > l && !tMap.containsKey(s.charAt(r))){
    
            r--;
        }
        if(l > r){
    
            return "";
        }
        //以上代码是在把s两端不在t中出现的字符全部剔除，再在剩下的字符串newS中查找符合条件的字符串
        String newS = s.substring(l,r + 1);
        //len记录运算过程中当前记录到的最小窗口的长度
        int len = 1000000000;
        int resl = 0;
        int resr = -1;
        //p1是窗口左边界，收缩窗口；p2是窗口右边界，扩大窗口
        int p1 = 0;
        //p2从负一开始是为了应对newS长度为一的情况，如样例s:"a",t:"a"
        int p2 = -1;
        //p2<newS.length() - 1很容易理解，窗口的右边界达到字符串末端时是滑动的终止条件
        //不过可能会出现p2到达字符串末端时，p1还可以再向右继续缩小窗口，因此还要加上一个p1<p2的条件
        while (p1 < p2 || p2 < newS.length() - 1){
    
            //只要当前窗口不符合条件p2都要不断右移
            while (p2 < newS.length() - 1 && !check()){
    
                p2++;
                char c = newS.charAt(p2);
                resMap.put(c,resMap.getOrDefault(c,0) + 1);
            }
            //当前窗口符合条件，就要更新len以及resl，resr,保证此时的len是最小的,resl和resr是相对应的字符串下标
            if(check() && p2 - p1 +  1 < len){
    
                len = p2 - p1 +  1;
                resl = p1;
                resr = p2;
            }
            //此时得到的窗口是符合条件的，所以可以开始缩小窗口往右遍历寻找更优解
            if(p1<p2){
    
            char c = newS.charAt(p1++);
            //p1一开始指向的肯定是t中有的字符，收缩的思路是找到下一个t中有的字符
            resMap.put(c,resMap.get(c) - 1);
            while (!tMap.containsKey(newS.charAt(p1))){
    
                p1++;
            }}
        }
        return (resr == -1) ? "" : newS.substring(resl,resr + 1);
    }
    public boolean check(){
    
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
    
            Character key = entry.getKey();
            Integer val = entry.getValue();
            if (resMap.getOrDefault(key, 0) < val) {
    
                return false;
            }
        }
        return true;
    }
}

674. 最长连续递增序列(在线处理/滑动窗口)

要求子序列必须是连续的。变量 l 维护当前遍历到的数所在的连续序列的长度，那么，当遍历到 nums[i] 时，如果 nums[i] > nums[i - 1]，l 就加一，否则 nums[i] 就应该作为新的递增序列的开头重新计算， l 置为 1

public int findLengthOfLCIS(int[] nums) {
    
    int len = nums.length;
    int l = 1,maxL = 1; //maxL维护最大长度。l初始化为1，对应 nums[0] 
    for(int i = 1;i < len;i++){
    
        if(nums[i] > nums[i - 1]){
    
            l++;
            maxL = Math.max(l,maxL);
        }
        else l = 1;
    }
    return maxL;
}

53.最大子数组和(在线处理/滑动窗口)

public int maxSubArray(int[] nums) {
    
    int sum = 0,max = Integer.MIN_VALUE;
    for (int num : nums) {
    
        if (sum < 0) {
    
            sum = 0;
        }
        sum += num;
        max = Math.max(max, sum);
    }
    return max;
}

从头开始遍历数组，用sum记录此时遍历到的子序列的元素和，如果sum小于 0，也就是说遍历到的子序列和小于 0，由于题目要求是子序列。那么这段元素和为 0 的子序列对后面的子序列来说就是累赘，因为不管后面序列的和为多少，如果要把这段和为 0 的子序列加上，整个序列的和都是变小的，所以如果当前sum小于 0，就要抛弃当前遍历到的子序列

面试题 17.24. 最大子矩阵

解题思路来自该题解
大概就是，对于每一行 i，将第 i 行到第 j 行 (j = i，i + 1，…，row - 1) 之间的所有行 “压榨” 为一个数，然后进行一维数组的 [最大子数组和] 求解

public int[] getMaxMatrix(int[][] matrix) {
    
    int row = matrix.length;
    int column = matrix[0].length;
    int maxSum = Integer.MIN_VALUE,r1 = 0,c1 = 0,r2 = 0,c2 = 0,sum,r1Tmp = 0,c1Tmp = 0;
    int[] rowSum = new int[column]; //当前被“压榨”的所有行中每一列的和
    for(int i = 0;i < row;i++){
      //对于每一行 i
        Arrays.fill(rowSum,0);
        for(int j = i;j < row;j++){
      //枚举 j
            sum = 0;
            for(int k = 0;k < column;k++){
     
                rowSum[k] += matrix[j][k];  //求i 到 j 行间所有行中每一列的和
                if(sum > 0) sum += rowSum[k]; 
                else{
        //前面的和小于0，那就弃掉，让当前列的和作为新的 sum，同时更新左上角的行列坐标
                    sum = rowSum[k];
                    r1Tmp = i;
                    c1Tmp = k;
                }
                if(sum > maxSum){
      //如果得到了比维护的子矩阵最大和还大的和，就更新维护答案的四个坐标以及maxSum
                    maxSum = sum;
                    r1 = r1Tmp;
                    c1 = c1Tmp;
                    r2 = j;
                    c2 = k;
                }
            }
        }
    }
    return new int[]{
    r1,c1,r2,c2};
}

363. 矩形区域不超过 K 的最大数值和

这道题下面的解法其实不太像滑动窗口，但思路上跟上面两道题非常相似，所以我就放到一起了。三道题建议一起比对
首先，根据题意是要枚举原矩阵中的部分矩形区域，也就是子矩阵，那么类似于上面的 [最大子矩阵] 题目，枚举一个子矩阵时将其每一行 “压缩” 为一个数，得到一个一维数组，这个一维数组每一个数就表示一行的元素总和，再计算这些行能组成的矩阵中，元素总和最大的那个总和即可，当然这个最大总和要求不大于 k

class Solution {
    
    public int maxSumSubmatrix(int[][] matrix, int k) {
    
        int rows = matrix.length, cols = matrix[0].length, max = Integer.MIN_VALUE;
        for (int l = 0; l < cols; l++) {
     // 枚举左边界
            int[] rowSum = new int[rows]; 
            for (int r = l; r < cols; r++) {
     // 枚举右边界
                for (int i = 0; i < rows; i++) {
    
                    rowSum[i] += matrix[i][r]; //累加计算左右边界之间每一行的元素总和
                }
                max = Math.max(max, findMax(rowSum, k)); //找到左右边界之间这些行可以组成的矩阵中，元素总和最大的那个总和
                if(max == k) return k; //找到等于k的答案直接返回，节约后续的运算，也算个剪枝
            }
        }
        return max;
    }
    private int findMax(int[] arr, int k) {
    
        int max = Integer.MIN_VALUE,sum;
        for (int i = 0;i < arr.length;i++) {
     //第i行可以和第i+1，...，第arr.length-1行之间连续的行组成矩阵
            sum = 0;
            for (int j = i; j < arr.length; j++) {
    
                sum += arr[j];
                if (sum > max && sum <= k) max = sum;
                if(max == k) return k;
            }
        }
        return max;

    }
}

可以看出来，其实 findMax() 函数就是在求 arr 数组的最大子数组和，只不过要求这个最大子数组和不超过 k，那么类似于 [最大子数组和]，可以做出如下优化：

class Solution {
    
    public int maxSumSubmatrix(int[][] matrix, int k) {
    
    	//...
        int[] rowSum = new int[rows];  //将rowSum的重新new操作改为全填充为0
        for (int l = 0; l < cols; l++) {
     // 枚举左边界
            Arrays.fill(rowSum,0);
            //...
        }
        return max;
    }
    private int findMax(int[] arr, int k) {
    
        int sum = 0,max = Integer.MIN_VALUE;
        for(int i : arr){
    
            if(sum < 0) sum = 0;
            sum += i;
            max = Math.max(max,sum);
        }
        if(max <= k) return max; //最大子数组和不超过k就满足，可以直接返回，否则就还是要按照原来那样算
        max = Integer.MIN_VALUE;
        sum = 0;
        for (int i = 0;i < arr.length;i++) {
    
            //...
        }
        return max;
    }
}