前言科普:什么是滑动窗口算法
滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。
假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有:
[a b c] [b c d] [c d e] [d e f] [e f g] [f g h]
一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动,同时 动态地 记录一些有用的数据,很多情况下,能够极大地提高算法地效率。
1. 滑动窗口最大值
题目来源于 LeetCode 上第 239 号问题:滑动窗口最大值。题目难度为 Hard,目前通过率为 40.5% 。
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例:
输入: 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
利用一个 双端队列,在队列中存储元素在数组中的位置, 并且维持队列的严格递减,,也就说维持队首元素是 **最大的 **,当遍历到一个新元素时, 如果队列里有比当前元素小的,就将其移除队列,以保证队列的递减。当队列元素位置之差大于 k,就将队首元素移除。
Deque 的含义是 “double ended queue”,即双端队列,它具有队列和栈的性质的数据结构。顾名思义,它是一种前端与后端都支持插入和删除操作的队列。
Deque 继承自 Queue(队列),它的直接实现有 ArrayDeque、LinkedList 等。
动画描述 Made by Jun Chen
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { //有点坑,题目里都说了数组不为空,且 k > 0。但是看了一下,测试用例里面还是有nums = [], k = 0,所以只好加上这个判断 if (nums == null || nums.length < k || k == 0) return new int[0]; int[] res = new int[nums.length - k + 1]; //双端队列 Deque<Integer> deque = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { //在尾部添加元素,并保证左边元素都比尾部大 while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) { deque.removeLast(); } deque.addLast(i); //在头部移除元素 if (deque.getFirst() == i - k) { deque.removeFirst(); } //输出结果 if (i >= k - 1) { res[i - k + 1] = nums[deque.getFirst()]; } } return res; } }
2. 无重复字符的最长子串
题目来源于 LeetCode 上第 3 号问题:无重复字符的最长子串。题目难度为 Medium,目前通过率为 29.0% 。
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
建立一个256位大小的整型数组 freg ,用来建立字符和其出现位置之间的映射。
维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。
动画描述
// 滑动窗口 // 时间复杂度: O(len(s)) // 空间复杂度: O(len(charset)) class Solution { public: int lengthOfLongestSubstring(string s) { int freq[256] = {0}; int l = 0, r = -1; //滑动窗口为s[l...r] int res = 0; // 整个循环从 l == 0; r == -1 这个空窗口开始 // 到l == s.size(); r == s.size()-1 这个空窗口截止 // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值 while(l < s.size()){ if(r + 1 < s.size() && freq[s[r+1]] == 0){ r++; freq[s[r]]++; }else { //r已经到头 || freq[s[r+1]] == 1 freq[s[l]]--; l++; } res = max(res, r-l+1); } return res; } };
3. 存在重复元素 II
题目来源于 LeetCode 上第 219 号问题:存在重复元素 II。题目难度为 Easy,目前通过率为 33.9% 。
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3 输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1 输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2 输出: false
使用用滑动窗口与查找表来解决。
动画描述
// 时间复杂度: O(n) // 空间复杂度: O(k) class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { if(nums.size() <= 1) return false; if(k <= 0) return false; unordered_set<int> record; for(int i = 0 ; i < nums.size() ; i ++){ if(record.find(nums[i]) != record.end()){ return true; } record.insert(nums[i]); // 保持record中最多有k个元素 // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素 if(record.size() == k + 1){ record.erase(nums[i - k]); } } return false; } };
4. 长度最小的子数组
题目来源于 LeetCode 上第 209 号问题:长度最小的子数组。题目难度为 Medium,目前通过率为 37.7% 。
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
定义两个指针 left 和 right ,分别记录子数组的左右的边界位置。
设置滑动窗口的长度为 0 ,位于数轴的最左端。
1 .滑动窗口右端 R 开始移动,直到区间满足给定的条件,也就是和大于 7 ,此时停止于第三个元素 2,当前的最优长度为 4
图 1
2. 滑动窗口左端 L 开始移动,缩小滑动窗口的大小,停止于第一个元素 3,此时区间和为 6,使得区间和不满足给定的条件(此时不大于 7)
图片 2
3. 滑动窗口右端 R 继续移动,停止于第四个元素 4,此时和位 10 ,但最优长度仍然为 4
图片 3
代码实现
// 滑动窗口的思路 // 时间复杂度: O(n) // 空间复杂度: O(1) class Solution { public int minSubArrayLen(int s, int[] nums) { int l= 0,r = -1; // nums[l...r]为我们的滑动窗口 int sum = 0; int result = nums.length + 1; while (l < nums.length){ // 窗口的左边界在数组范围内,则循环继续 if( r+1 <nums.length && sum < s){ r++; sum += nums[r]; }else { // r已经到头 或者 sum >= s sum -= nums[l]; l++; } if(sum >= s){ result = (r-l+1) < result ? (r-l+1) : result ; } } if(result==nums.length+1){ return 0; } return result; } }