滑动窗口的经典问题

最长子串问题

L3 无重复字符的最长子串

给定一个字符串 s ,请你找出其中不含有重复字符的 最长

子串

的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

要找最长子串,必然要知道无重复字符串的首和尾,然后再从中确定最长的那个,因此至少两个指针才可以,这就想到了滑动窗口思想。

在解这道题前,首先需要对子串认识一下,假设有字符串abca,他的子串就有:a,b,c,ab,ac,bc,abc,bca,等

但是如果我们单纯使用双指针,可能会比较复杂,所以这里使用Map来记录

这里我们思路是这样的:

  1. 定义left和right,使用Map记录每一个出现过的字母,当right到重复的a时,此时找到子串abc,a重复,更新Map中a的索引
  2. 之后,left要移动的位置恰好就是map.get(’a‘) + 1=1,right继续找到子串bca整体过程就是:先更新left,然后将Map中的索引更新为新的索引

依次类推是这样,但是这里有一点需要注意不能误会:

right假设找到的是重复字符串a,那么left要移动到map.get(’a‘) + 1处,这点很关键

另一个需要注意的就是特殊情况:

例如abba,我们第二次访问b时,left=map.get(’b‘) + 1=2。

然后继续访问第二个a,此时left=map.get(’a‘) + 1=1,也就是left后退了,显然不对。

因此这里我们需要和原来的对比一下,将最大的加1就可以

image-20240412101456877

知道了流程,我们来代码实现

class Solution {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) return 0;
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int res = 0;
        for (int right = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            
            map.put(s.charAt(right), right);
            res = Math.max(res,right - left+1);
        }
        return res;
    }
}

这里解决了,但是需要注意两个小细节:

  1. 求res的时候,因为right-left时,假设第一次,right=2,left=0,这个时候的长度并非我们需要,而等right到a的时候,left此时已经为1,更不合我们的预期,所以我们+1
  2. 第二个细节是:map.get(s.charAt(right)) + 1,这里我们需要left到下一个,所以需要+1

L159 至多包含两个不同字符的最长子串

给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t ,并返回该子串的长度,这就是LeetCode159题。例如:

输入: "eceba"
输出: 3
解释: t 是 "ece",长度为3。

这道题依然是和上道题一样,使用map,但是我们需要考虑两个问题:

  1. 如何维护Map内固定只有两个元素呢?
  2. 我们应该怎么删除元素?

假设我们有这样的字符串:aabbcccd

首先我们看过程:

首先,我们需要的是:

  1. 假设遇到c的时候,我们下一次进行检查,应该检查的是最后一个a出现的索引+1,这时候删除的是s.chatAt(1),下一次到d的时候,我们需要检查的是b最后一个索引+1,删除也是该索引
  2. 当我们删除掉元素后,这个时候我们需要的应该是正常添加元素,然后利用map覆盖的特性,(假设这里是c),将新的元素最后一个value值存入到map当中
  3. 当计算maxLen的时候,因为特殊情况已经被我们排除,maxLen只需要定义为需要k个不同元素的数即可,下面计算的时候,也只需要right-left,如下图【1】,求出子串的长度

image-20240413184632820

这里得到代码

 public static int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() < 3) return s.length();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        int maxLen = 2;
        while (right < s.length())
            if (map.size() < 3) {
                map.put(s.charAt(right), right++);
            }
        if (map.size() == 3) {
            int min = Collections.min(map.values());
            map.remove(s.charAt(min));
            left = min + 1;
        }
        maxLen = Math.max(maxLen, right - left);
        return maxLen;
    }

L340 至多包含 K 个不同字符的最长子串

理解了上道题的实现,这里很简单无非是照猫画虎:

 public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length()<k+1)return s.length();
        Map<Character, Integer> map = new HashMap<>();
        int left =0,right = 0;
        int maxLen = k;
        while (right<s.length()){
            if(map.size()<k+1){
                map.put(s.charAt(right),right++);
            }
            if (map.size()==k+1){
                int  min = Collections.min(map.values());
                map.remove(s.charAt(min));
                left = min+1;
            }
            maxLen = Math.min(maxLen, right - left);
        }
        return maxLen;
    }

L209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组

[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

通过上面两道题对滑动窗口和双指针的思想,这里的实现并不难:

class Solution {
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int res = 100001;
        int sum = 0;
        while (right < nums.length && left < nums.length) {
            sum += nums[right++];
            if (sum >= target) {
                res = Math.min(res, right - left++);
                sum = 0;
                right = left;
            }
        }
        return res == 100001 ? 0 : res;
    }
}

但是!这种做法的重复度太高了,我们相当于每一次算出符合的子数组后,接下来又要从;left+1处重新计算sum

解决方法也很简单:我们算出来的sum能否直接减去left,在这个结果上继续判断和target的关系,然后继续right++计算呢?

简单调整:

class Solution {
   public static int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0) return 0;
        int left = 0, right = 0;
        int res = 100001;
        int sum = 0;
        while (right < nums.length ) {
            sum += nums[right++];
            while (sum >= target) {
                res = Math.min(res, right - left);
                sum-= nums[left++];
            }
        }
        return res==100001?0:res;
    }
}

这一步很巧妙,因为当在此寻找target的时候,不需要从左往右,因为一开始的right++,已经找到了左到右符合条件的部分,因此,left也不可能比right大,所以不需要判断left越界

L11 盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0)(i, height[i])

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明:**你不能倾斜容器。寻找子串异位词(排列)

image-20240413202644607

看到这道题首先需要分析,什么时候面积最大呢?

面积公式可以很明显求出: S(i,j)=min(h[i],h[j])×(j−i)

那么问题来了,我们应该怎么分配双指针呢?

  1. 都从最左边开始,依次right++吗? 很明显这样太复杂了,我们需要找到面积增大的规律

  2. 我们首先从两边开始包围面积,left=0,right=len-1;当任意一个left或者right移动后,宽一定会 -1,因此我们如果遇见下一个长度和这个长度一样时,一定会减小;

  3. 在这里想要面积增大,除非我们移动的短板比原来大,面积才会更大、相等,所以总结有以下规律:

  • 若向内移动短板 ,水槽的短板min(h[i],h[j]) 可能变大,因此下个水槽的面积可能增大 。
  • 若向内移动长板 ,水槽的短板min(h[i],h[j]) 不变或变小,因此下个水槽的面积一定变小

所以我们有以下代码:

class Solution {
    public int maxArea(int[] height) {
         if (height.length < 2) return 0;
        int left = 0, right = height.length-1;
        int area = 0;
        while (left<right) {
           area = height[left]<height[right]?
                   Math.max(area,(right-left)*height[left++]):
                   Math.max(area,(right-left)*height[right--]);

        }
        return area;   
    }
}

寻找子串异位词(排列)

L567 字符串的排列

给你两个字符串 s1s2 ,写一个函数来判断 s2 是否**包含 s1 的排列。**如果是,返回 true ;否则,返回 false

换句话说,s1 的排列之一是 s2子串

示例 1:

输入:s1 = "ab" s2 = "eidbaooo"
输出:true
解释:s2 包含 s1 的排列之一 ("ba").

示例 2:

输入:s1= "ab" s2 = "eidboaoo"
输出:false

提示:

  • 1 <= s1.length, s2.length <= 104
  • s1s2 仅包含小写字母

看到这道题首先想到的是判断出现过s1中的字符在s2中也出现过就可以了,这样是没错,但是忽略了一点,题目要求的是包含s1的排列,很明显如果上述做法示例2,很明显是错误的

正确的做法依然是滑动窗口,假如我们使用固定窗口然后判断是否存在s1中字符,就可以实现了,那么具体步骤呢?

这里实现也很简单,只需要也定义一个窗口始终和s1中判断就行,这里的窗口我们可以使用Map也可以定义一个26长度的数组,因为只有小写字母

具体代码:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
            return false;

        int[] num1 = new int[26];
        int[] num2 = new int[26];
        int len = s1.length();
        for (int i = 0; i < len; i++) {
            num1[s1.charAt(i) - 'a']++;
            num2[s2.charAt(i) - 'a']++;
        }
        // 这里首先判断此时是否已经成立,否则继续在num2中继续移动窗口
        if (Arrays.equals(num1, num2)) {
            return true;
        }
        for (int right = len; right < s2.length(); right++) {
            num2[s2.charAt(right) - 'a']++;
            int left = right - len;
            num2[s2.charAt(left) - 'a']--;
            if (Arrays.equals(num1, num2)) {
                return true;
            }

        }

        return false;
    }
}

L438 找到字符串中所有字母异位词

给定两个字符串 sp,找到 s 中所有 p异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • sp 仅包含小写字母

这道题基本思路一致,但是需要注意:

  1. 当我们窗口滑动继续使用right的时候,我们发现当right到最后一个的时候,窗口是无法滑动到最后的,因此我们换一种思路,使用left指针
  2. 还有一个注意的就是,如果不提前将窗口内的结果加入结果集,始终会出现上述情况
  3. 最后的left+1是为了能够让此时提起移动的窗口加入对应的值
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> res = new ArrayList<>();
        if (s.length() < p.length())
            return res;
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        int len = p.length();
        for (int i = 0; i < len; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(pCount, sCount)) {
            res.add(0);
        }
        for (int left = 0; left <s.length()-len ; left++) {
            int right = left+len;
            sCount[s.charAt(right)-'a']++;
            sCount[s.charAt(left)-'a']--;
            if (Arrays.equals(pCount,sCount)){
                res.add(left+1);
            }
        }
        return res;

    }
}

滑动窗口与堆的结合

L239 滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2:

输入:nums = [1], k = 1
输出:[1]

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

这道题的意思是每次找出滑动窗口的最大值,一开始我们有种想法是:每次记录最大值不就好了吗,但是深入分析的话,我们发现,求和的时候我们加后一个,减去前一个就好,但是这里我们如果减去后一个,每次我们并不知道此时标注的当前最大值是否还在窗口内,所以这种处理方法并不简单。

对于最大值、K个最大这种场景,优先队列(堆)是首先应该考虑的思路,所以这里我们根据最大值,想到了堆

在这里首先我们对堆(优先队列)进行复习,优先队列默认是小顶堆,构造方法可以通过定义比较器来改变

比较器又有:基于compare方法的约定,即:

  • 如果compare(a, b)返回一个正数,这意味着a应该排在b之后。
  • 如果compare(a, b)返回一个负数,这意味着a应该排在b之前。

在这道题,我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素num 在数组中的下标为index。

实现:

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
            (o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1]);

具体代码实现:

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[1]);
        for (int i = 0; i < k; i++) {
            pq.offer(new int[] { nums[i], i });
        }
        //这里先将第一个窗口最大值加入(n-k+1)就是答案需要的数组长度
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int right = k; right < n; right++) {
            pq.offer(new int[] { nums[right], right });
            while (pq.peek()[1] <= right - k) {
                pq.poll();
            }
            //计算出ans索引
            ans[right - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

这里可能难理解的是while中的条件,这里的过程是这样的:当堆顶不断添加元素变化的时候,假设我们有数组nums = [10, 9, 8, 7, 6]k = 3。当滑动窗口从最开始的[10, 9, 8]移动到[9, 8, 7]时,元素10(索引0)需要从队列中移除,这个时候如果不删除已经在窗口外的元素,会影响后续堆的判断

复杂度分析

  • 时间复杂度:O(nlogn)其中 n 是数组 nums 的长度。最坏情况下,数组是递增的,

  • 最终优先队列中包含了所有元素,没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn),因此总时间复杂度为 O(nlog⁡n)

  • 空间复杂度:O(n)即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间,只计算额外的空间使用。

优化

现在我们重新细致的讨论这道题,我们知道如果单纯只从窗口右边增加,左边不动的话,时间复杂度是O(1),但是这样会有刚才提到的,左边缩小的值恰好是最大值这种情况,所以我们只能O(j-i),遍历整个窗口的最大值:

时间复杂度为:O((n-k+1)K),而n-k+1就是窗口数量,获取每一个窗口最大值的时间复杂度为O(K)

也就是说,这道题最大的难点在于从窗口获取最大值的时间复杂度降低到O(1)

单调队列的解法

这里使用的单调队列

K神:回忆 最小栈 ,其使用 单调栈 实现了随意入栈、出栈情况下的 O(1) 时间获取栈内最小值。本题同理,不同点在于 “出栈操作” 删除的是 “列表尾部元素” ,而 “窗口滑动” 删除的是 “列表首部元素” 。

大致过程就是始终维护一个双端的队列,这个队列单调递减,因此保证了第一个数是最大的

每一次窗口移动后,在添加新元素前,需要判断最后一个元素是否大于当前right指针元素,如果新加的元素要比队列内最后一个元素大,那就需要删除队里内的元素,维持双端队列的单调性

而if (deque.peekFirst() == nums[right - k])为了判断,是否此时left指针的元素是此时的最大值,如果是最大值则需要删除

class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0)
            return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        //未形成窗口
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        for (int right = k; right < nums.length; right++) {
            // 处理移动窗口,判断是否需要删除当前最大的元素
            if (deque.peekFirst() == nums[right - k]) {
                deque.removeFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[right])
                deque.removeLast();
            deque.addLast(nums[right]);
            res[right - k + 1] = deque.peekFirst();
        }
        return res;

    }
}