滑动窗口详解 |
您所在的位置：网站首页 › 滑动动作 › 滑动窗口详解 |
滑动窗口详解
|
滑动窗口
基本概念
滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。 分类：窗口有两类，一种是固定大小类的窗口，一类是大小动态变化的窗口。 应用： 利用滑动窗口获取平滑的数据，如一段连续时间的数据平均值，能够有更好的稳定性，如温度监测。 什么情况可以用滑动窗口来解决实际问题呢？ 一般给出的数据结构是数组或者字符串求取某个子串或者子序列最长最短等最值问题或者求某个目标值时该问题本身可以通过暴力求解 核心思路窗口的形成 在具体使用之前，我们知道窗口实际是两个指针之间形成的区域，那关键就是这两个指针是如何移动的。 初始时，左右指针left,right都指向第0个元素，窗口为[left,right)，注意这里是左闭右开，因此初始窗口[0,0)区间没有元素，符合我们的初始定义 开始循环遍历整个数组元素，判断当前right指针是否超过整个数组的长度，是退出循环，否则执行第3步 然后right指针开始向右移动一个长度，并更新窗口内的区间数据
这中间，窗口的更新与维护是很重要的一环，新元素加入窗口，旧元素移出窗口，都需要及时地更新与这个窗口范围相关的数据。 上述说明主要是两个while循环，可以简单抽象成一个模板如下： int left = 0,right =0; while(right指针未越界){ char ch = arr[right++]; //右指针移动，更新窗口 ... //窗口数据满足条件 对于固定窗口而言，就是窗口的大小>=固定值；对于动态窗口，就是从left出发，窗口不断扩充，第一次满足题意的位置 while(窗口数据满足条件){ //记录或者更新全局数据 ... //右指针不动，左指针开始移动一位 char tmp = arr[left++]; //左指针移动，窗口缩小，更新窗口数据 ... } //返回结果 ... }下面就结合所说的方法来看实际的栗子，主要的变化是窗口数据满足的条件，应该根据不同的要求来具体实现。 实战 LC438. 找到字符串中所有字母异位词 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 分析题目的意思从字符串s中选取固定长度的子串，使得子串和给出的p字符串的字符种类相同，且每一种字符的数量也相同，称之为异位词。要求求出所有符合要求的子串的起始位置。 暴力的解法是选取所有子串然后与给定的字符串p进行比较，复杂度较高。 使用滑动窗口的方法来解决，并且是个固定大小的滑动窗口。 窗口内数据满足条件后，开始进行收缩，这个条件是窗口内的字符串和给出的字符串，字符种类一样，且每一类字符的数量也一致。从这个描述来看可以使用两个个map来记录数据，一个记录窗口内的字符种类和数量，记作window，这个map需要根据窗口的变化来实时更新；一个记录给定字符串的种类和数量，记作map，这是一个固定的map，不会更新。 如果存在一个窗口，window和map相同，即字符种类和大小完全一样，那么当前的left是一个可行的位置，将其添加到集合。那如何判断map和window是一样的呢？暴力的方法，就是按每类字符去对比，字符种类一样，每类数量一致，复杂度是O(n)，那有没有更好的方法呢？ 事实上，我们就是要在移动指针形成窗口的过程中，判断window和map是否一致。map是固定的，可以按每一类字符来比较，初始化一个计数器valid=0，如果窗口内某类字符完全一致，那么valid加1，最后如果valid==map.size()那么说明我们找到了一个解。 当然我们引入的valid，就需要根据窗口的更新来更新。 窗口更新（移入数据） 更新window：如果该字符在map中，那么需要加入到window计数器中；否则计数器不更新 更新valid：数据移入窗口时，如果当前字符在给定的map中，我们要的字符种类出现了，如果这类字符的数量和给定map中该类字符的数量也一致，那么说明该类字符我们就搞定了。 窗口更新（移出数据） 更新valid：数据移出窗口时，如果该字符在map中，说明是我们要处理的字符，其字符数量和map中一致时，此时要移出窗口，valid要减1。 更新window：如果该字符在map中，那window计数器对于该计数器需要减1 具体代码如下： public List findAnagrams(String s, String p) { List res = new ArrayList(); Map map = new HashMap(); Map window = new HashMap(); char[] pattern = p.toCharArray(); char[] arr = s.toCharArray(); for (char a : pattern) { map.put(a, map.getOrDefault(a, 0) + 1); } int left = 0, right = 0; int valid = 0; while (right //加入窗口 window.put(ch, window.getOrDefault(ch, 0) + 1); // 不能写== 比较的是两个地址 if (window.get(ch).equals(map.get(ch))) { valid++; } } //判断窗口内元素是否满足条件,两个条件：1）固定窗口，当前窗口数量等于 模式字符串p的长度 2)当前窗口内组成的字符串和模式字符串 是异位词 while (right - left == p.length()) { //固定窗口，判断当前窗口是否是异位词,如果是说明找到了一个位置，把left加入到结果集中 if (valid == map.size()) { res.add(left); } //right 不动，左指针开始向右，arr[left]元素移出窗口,同时该元素在window中对于的数目也要减去1 char tmp = arr[left]; left++; if (map.containsKey(tmp)) { if (map.get(tmp).equals(window.get(tmp))) { valid--; } window.put(tmp, window.get(tmp) - 1); } } } return res; } LC76. 最小覆盖子串 分析和LC438很相似，但是本题是一个动态窗口，解题方法同LC438也一致，只是不需要对窗口的大小进行限制。当窗口内的数据满足条件时，就可以进行窗口的收缩了。 代码如下： public String minWindow(String s, String t) { int start = 0, len = s.length() + 1; char[] pattern = t.toCharArray(); char[] arr = s.toCharArray(); Map map = new HashMap(); Map window = new HashMap(); for (char a : pattern) { map.put(a, map.getOrDefault(a, 0) + 1); } int left = 0, right = 0, valid = 0; while (right window.put(ch, window.getOrDefault(ch, 0) + 1); if (window.get(ch).equals(map.get(ch))) { valid++; } } //满足条件的窗口 这里不是固定窗口，对窗口大小不限制，当map和window中的数据一致，满足条件，开始收缩 while (valid == map.size()) { // 当前已经满足要求，更新并记录数据，同时收缩窗口 if (right - left // 当前要移出的字符种类和数量和map一致，移出后不一致，valid-- if (window.get(tmp).equals(map.get(tmp))) { valid--; } window.put(tmp, window.get(tmp) - 1); } } } return len == s.length()+1 ? "" : s.substring(start, start + len); }事实上，当valid==map.size()时，在窗口window内可能出现比map中对应字符数量多的情况，但是valid并没有变大，是因为在更新valid的时候，只有与map中字符数目相同才更新，如果已经满足了该条件，那么只更新window，不更新valid。 举个例子，s=“BBNAC”，t=“ABC” 第一个满足条件的窗口，B字符出现了2次，但map中只出现了1次。 在移出的时候，只有当当前窗口中该移出字符的数量刚好等于map中该字符的数量时，valid才会-1，表示当前窗口已经不满足要求了，第二个while循环也就不会再继续了，又开始进行right指针的移动了。 本文对滑动窗口类的一些问题进行了分析，总结了一个模板，并结合Leetcode上的一些例子进行了应用实战。Leetcode相关类型的例子还有LC3、LC513、LC1052等，可以参考利用上述方法进行练习。 迟来的本周更新总算赶上了，希望后续能够保持，与君共勉！ 更多信息可关注微信公众号:惊鸿只为卿 欢迎点赞、关注、分享、在看！ |
【本文地址】