亲宝软件园·资讯

展开

LeetCode(239.滑动窗口的最大值

de_de 人气:0
#### 题目: 给定一个数组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 **初始思路**:刚开始没想太多,C++中求数组的最大值的函数:max_element可以解决此问题。果不其然,AC了而且时间复杂度也很高。显然不是这个题目的正常解法,一番苦思冥想后还是打开了题解区。卧槽!哟嘚斯内!下面我就能分析下大佬的方法。 **单调队列解法**: 一个普通队列输入什么数那位置就是什么数,而单调队列在输入一个数时会与前面的比较大小,删除部分元素来保证队列的数是**单调递增或递减**的。 这样在这个题目中,每次向右移动都会增删一个元素,但我们要在**线性时间**找到最大值,我们就可以考虑单调队列。 单调队列通常有这几个函数: class MonotonicQueue { // 在队尾添加元素 n void push(int n); // 返回当前队列中的最大值 int max(); // 队头元素如果是 n,删除它 void pop(int n); } 然后我们假设已经有了单调队列这个数据结构来满足我们的要求,我们可以把此题的解题框架搭出来: vector

加载全部内容

相关教程
猜你喜欢
用户评论