算法面试通关 40 讲
覃超
Sophon Tech 创始人,前 Facebook 工程师,卡内基梅隆大学计算机硕士
78356 人已学习
新⼈⾸单¥68
课程目录
已完结/共 62 讲
第二章:理论讲解+面试题实战 (53讲)
算法面试通关 40 讲
登录|注册
留言
87
收藏
沉浸
阅读
分享
手机端
回顶部
当前播放: 12 | 面试题:返回滑动窗口中的最大值
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.75x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
01 | 合格程序员的第一步:算法与数据结构
02 | 如何事半功倍地学习算法与数据结构
03 | 如何计算算法的复杂度
04 | 如何通过LeetCode来进行算法题目练习
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
登录 后留言

全部留言(87)

  • 最新
  • 精选
andi轩
看前面很多人评论的问题,其实老师白班讲解由[3,-1,-3],5变成3,[-1,-3,5]的时候,出队顺序会让人误解,其实应该是维护队列需要从两边出队,也就是先把3从左边出队,然后判断-3<5,把-3从右边出队,再把-1出队,最后把5从右边入队

作者回复: 对的。

2019-04-26
7
41
子青
看一个数组:1,3,1,2,0,5 window也设为3。会移动到这步:deque:[3,1,2],再下一步变为:[1,2,0] 此时deque中第一个元素(也就是最大元素)是1而不是2!

作者回复: 2进入window的时候,会把前面的那个1先顶出window.

2018-10-15
4
21
web
Java 版本答案 public int[] maxSlidingWindow(int[] nums, int k) { if(nums.length==0) return new int[0]; int[] res = new int[nums.length - k + 1]; Deque<Integer> deque = new ArrayDeque<>(); for(int i=0;i<nums.length;i++) { // 删除队列中小于窗口左边下标的元素 if(i >= k && i - k + 1 > deque.peek()) deque.remove(); // 从队列右侧开始, 删除小于nums[i] 的元素 while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast(); deque.add(i); // 队列左侧是最大值,加入结果 if(i - k + 1 >= 0) res[i - k + 1] = nums[deque.peek()]; } return res; }

作者回复: 帅!!

2019-02-26
4
16
雷朝建
我在写此类算法题时候,使用的是JS语言, 所以直接编写如下的代码: var maxSlidingWindow = function(nums, k) { if (nums.length === 0) return nums; const r = []; for (let i = k; i <= nums.length; i++) { r.push(Math.max(...nums.slice(i - k, i))); } return r; }; 我当时还特别疑惑为什么此题的难度为hard。 编程语言有时候会限制个人的思维, 前端的代码没有遇到过复杂的数据结构, 导致一些思路根本打不开,这也是我需要克服的一点。

作者回复: 好的总结和回顾! 👍🏻

2019-01-06
6
7
冰梨icePear🍐
我的理解一种算法比另外种在当前环境下更优一定是有地方解决了前一种算法的哪里做的无用功,这个例子里deque是不是就是避免了堆中需要重排的这部分无用功从而优化了性能?有一点不理解的地方为什么用deque,我看并没有从右边出列的情况,使用普通的队列为什么不行呢?

作者回复: 这是一个很好的问题。首先为什么用deque,就是因为在插入的时候,需要从 window 左边移除元素,而下标出了 window 之后,需要用右侧移除。回到你前半部分的理解:算法更优是因为有地方解决了前一种算法做的无用功,这个正确:这里我们不需要用堆去维护window里k个元素的大小顺序,只需要记录最大值,所以用heap有点杀鸡用牛刀的意思。

2018-10-22
4
5
L*Z*田
老师,有一种情况, [6,4,5,3,2,1],k=3, 当3入队时,6出队,因为4和5都比3大,所以需要重新判断窗口中哪个数值最大,这部分的时间复杂度是不是忘记算了?

作者回复: 4在5被加入的时候就已经出去。由于每个元素只在window里呆一次,所以操作window的复杂度不和循环进行嵌套了。

2018-10-18
3
周军5656
deque没有维护第二大数字,当最大值移除后,是否要重新算最大值?

作者回复: 对的,需要的。只是按照我们开始的算法,最大数出去之后,剩下的第二个数就是window-k里的最大数。

2018-10-13
3
Yang
每个元素进队列后,是需要判断是否要干掉前面的数的吧,这个时间不用算吗?

作者回复: 这个判断的时间是常数时间,不会在里面嵌套O(n)的时间,因为在全部循环操作中,每个元素都只进入k window一次

2018-10-11
2
3
老师讲得非常棒,但是我最困惑的一点是,window窗口维护的是序列号,而不是具体的值,,这是我最困惑的一点,导致后面花了很多时间,一直没理解这个答案,我就是喜欢跳着看内容,,,, 好吧~_~,问题最终还是解决了。。。。

作者回复: 下次这种情况直接看解答和代码,理解了之后自己再回过头来反复写。

2019-05-22
1
Hurt
老师 两个 循环了 为什么时间复杂度是 On 的呢 没看懂这里老师

作者回复: 好问题。因为两层循环每层并不是跑满 o(n)。虽然是两层循环,但是从最后效果看,每个元素只被放入和拿出window一次,所以还是线性的时间复杂度。

2018-12-11
1
收起评论