分享几道和「滑动窗口」有关的算法面试题

前言科普:什么是滑动窗口算法

滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。

假设有数组 [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,就将队首元素移除。

补充:什么是双端队列(Dqueue)

Deque 的含义是 “double ended queue”,即双端队列,它具有队列和栈的性质的数据结构。顾名思义,它是一种前端与后端都支持插入和删除操作的队列。

Deque 继承自 Queue(队列),它的直接实现有 ArrayDeque、LinkedList 等。

动画描述

代码实现

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 ,用来建立字符和其出现位置之间的映射。

维护一个滑动窗口,窗口内的都是没有重复的字符,去尽可能的扩大窗口的大小,窗口不停的向右滑动。

(1)如果当前遍历到的字符从未出现过,那么直接扩大右边界;
(2)如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符;
(3)重复(1)(2),直到左边索引无法再移动;
(4)维护一个结果res,每次用出现过的窗口大小来更新结果 res,最后返回 res 获取结果。

动画描述

代码实现

// 滑动窗口
// 时间复杂度: 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

题目解析

使用用滑动窗口与查找表来解决。

  • 设置查找表record,用来保存每次遍历时插入的元素,record的最大长度为k
  • 遍历数组nums,每次遍历的时候在record查找是否存在相同的元素,如果存在则返回true,遍历结束
  • 如果此次遍历在record未查找到,则将该元素插入到record中,而后查看record的长度是否为k + 1
  • 如果此时record的长度是否为k + 1,则删减record的元素,该元素的值为nums[i - k]
  • 如果遍历完整个数组nums未查找到则返回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 ,分别记录子数组的左右的边界位置。

(1)让 right 向右移,直到子数组和大于等于给定值或者 right 达到数组末尾;
(2)更新最短距离,将 left 像右移一位, sum 减去移去的值;
(3)重复(1)(2)步骤,直到 right 到达末尾,且 left 到达临界位置

动画描述

设置滑动窗口的长度为 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;
 }
}

总结

以上所述是小编给大家介绍的分享几道和「滑动窗口」有关的算法面试题,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

(0)

相关推荐

  • PHP的文件操作与算法实现的面试题示例

    操作文件 1.使用5种以上的方式获取一个文件的扩展名 要求: dir/upload.image.jpg, 找出.jpg或者jpg <?php /** * 五种方式获取指定路径的文件扩展名 */ $str = "dir/upload.image.jpg"; function one ($str) { $arr = explode('.', $str); $count = count($arr); return $arr[$count - 1]; } function two ($s

  • JS面试题---关于算法台阶的问题

    有100格台阶,可以跨1步可以跨2步,那么一个有多少种走法: 今天电话面试.遇到一道算法问题,然后瞬间一脸懵逼: 然后机智的我,自作聪明的想到如果一个人每次都走1步,那么最多100步,每次走2步最少50步:然后明显跑题了...还好对方及时把我打断了...不然我估计要对着这玩意一直死脑经...一路走到黑.. 然后回到家了.拿着偶的mac,然后静静的思考,终于写出来了 var Stairs = new step(); function step(){ this.n1=1; this.n2=2; th

  • C#常见算法面试题小结

    本文实例汇总了C#面试常见的算法题及其解答.具有不错的学习借鉴价值.分享给大家供大家参考.具体如下: 1.写出冒泡,选择,插入排序算法. //冒泡排序 public class bubblesorter { public void sort(int[] list) { int i, j, temp; bool done = false; j = 1; while ((j < list.Length) && (!done)) { done = true; for (i = 0; i &

  • jQuery实现仿微软首页感应鼠标变化滑动窗口效果

    本文实例讲述了jQuery实现仿微软首页感应鼠标变化滑动窗口效果.分享给大家供大家参考.具体如下: 这是一款jQuery仿微软首页感应鼠标变化的滑动窗口,鼠标放上后,窗口会向左拉长,鼠标移走后恢复原样,是在微软官方网站发现的,看了看代码,觉得很容易就扣下来,不敢独享. 运行效果截图如下: 在线演示地址如下: http://demo.jb51.net/js/2015/jquery-f-microsoft-web-nav-demo/ 具体代码如下: <!DOCTYPE html PUBLIC "

  • 分享几道和「滑动窗口」有关的算法面试题

    前言科普:什么是滑动窗口算法 滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合. 假设有数组 [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

  • 几道和「黑洞照片」那种海量数据有关的算法问题

    昨晚被一则新闻刷屏:北京时间 4 月 10 日今晚 9 点,人类首张黑洞照片正式发布. 看到这张图片,小吴心里是极为震撼的:爱因斯坦太太太太太牛逼了!!! 同时,看新闻的时候小吴还注意到里面有个细节,给黑洞"拍照"的事件视界望远镜从 2017 年就开始为黑洞拍照了,但直到 2019 年才公布. 心里不禁纳闷:为什么给黑洞拍照需要这么长时间? 于是去更加详细的搜索资料,果然发现了端倪,其中一个点就是 望远镜观测到的数据量非常庞大 ! 2017 年时 8 个望远镜的数据量达到了 10PB(

  • go redis实现滑动窗口限流的方式(redis版)

    之前给大家介绍过单机当前进程的滑动窗口限流 , 这一个是使用go redis list结构实现的滑动窗口限流 , 原理都一样 , 但是支持分布式 原理可以参考之前的文章介绍 func LimitFreqs(queueName string, count uint, timeWindow int64) bool { currTime := time.Now().Unix() length := uint(ListLen(queueName)) if length < count { ListPus

  • Java 滑动窗口最大值的实现

    一.题目 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧.你只可以看到在滑动窗口内的 k 个数字.滑动窗口每次只向右移动一位. 返回滑动窗口中的最大值. 二.单调队列解析 题目让求随着滑动窗口的滑动,返回窗口覆盖范围的最大值 该题不适合优先级队列,因为采用大顶堆存放k个数字,可以知道此时的最大值,但是窗口是滑动的,大顶堆每次只能弹出最大值,无法移除其他值,即无法用大顶堆维护滑动窗口里的值. 所以采用队列维护,随着窗口的移动,队列先进先出 此时对队列的要求

  • ASP.NET Core中使用滑动窗口限流的问题及场景分析

    目录 算法原理 漏检 太刚 算法实现 进程内即内存滑动窗口算法 基于Redis的滑动窗口算法 应用算法 1.安装Nuget包 2.使用中间件 滑动窗口算法用于应对请求在时间周期中分布不均匀的情况,能够更精确的应对流量变化,比较著名的应用场景就是TCP协议的流量控制,不过今天要说的是服务限流场景中的应用. 算法原理 这里假设业务需要每秒钟限流100次,先来看固定窗口算法的两个问题: 漏检 如下图所示,单看第1秒和第2秒,其请求次数都没有超过100,所以使用固定窗口算法时不会触发限流.但是第1秒的后

  • 基于Redis zSet实现滑动窗口对短信进行防刷限流的问题

    前言 主要针对目前线上短信被脚本恶意盗刷的情况,用Redis实现滑动窗口限流 public void checkCurrentWindowValue(String telNum) { String windowKey = CommonConstant.getNnSmsWindowKey(telNum); //获取当前时间戳 long currentTime = System.currentTimeMillis(); //1小时,默认只能发5次,参数smsWindowMax做成可配置项,配置到Na

  • ASP.NET Core基于滑动窗口实现限流控制

    目录 前言: 二.固定窗口算法 三.滑动窗口算法 四.实现 六.使用 结论: 前言: 在实际项目中,为了保障服务器的稳定运行,需要对接口的可访问频次进行限流控制,避免因客户端频繁请求导致服务器压力过大. 而​AspNetCoreRateLimit是目前ASP.NET Core下最常用的限流解决方案. 查看它的实现代码,我发现它使用的固定窗口算法. var entry = await _counterStore.GetAsync(counterId, cancellationToken); if

  • redis zset实现滑动窗口限流的代码

    目录 限流 rediszset特性 滑动窗口算法 java代码实现 补充:RediszSet实现滑动窗口对短信进行防刷限流 前言 示例代码 限流 需求背景:同一用户1分钟内登录失败次数超过3次,页面添加验证码登录验证,也即是限流的思想. 常见的限流算法:固定窗口计数器:滑动窗口计数器:漏桶:令牌桶.本篇选择的滑动窗口计数器 redis zset特性 Redis 有序集合(sorted set)和集合(set)一样也是 string 类型元素的集合,且不允许重复的成员.不同的是每个元素都会关联一个

  • Java C++分别实现滑动窗口的最大值

    目录 1.题目 2.思路 3.c++代码 4.java代码 1.题目 给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值. 示例: 提示: 你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小. 2.思路 (单调队列) O(n) 给定一个数组 nums 和滑动窗口的大小 k,让我们找出所有滑动窗口里的最大值. 样例: 如样例所示,nums = [1,3,-1,-3,5,3,6,7],k = 3,我们输出[3,3,5,5,6,7]. 首先,我

随机推荐