37-算法打卡-栈与队列-滑动窗口最大值-leetcode(239)-第三十七天
1 题目地址
239. 滑动窗口最大值 - 力扣（LeetCode）239. 滑动窗口最大值 - 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。 示例 1：输入：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示例 2：输入：nums = [1], k = 1输出：[1] 提示： * 1 <= nums.length <= 105 * -104 <= nums[i] <= 104 * 1 <= k <= nums.length
https://leetcode.cn/problems/sliding-window-maximum/description/
2 题目说明
给你一个整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1 输出：[1]提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
3 解题思路
3.1 暴力方式
每次移动滑动窗口，比较窗口内的数据取出最大值，时间复杂度O(n*k)，不推荐使用
3.2 单调队列(待补充)
百度百科：即单调递减或单调递增的队列。使用频率不高，但在有些程序中会有非同寻常的作用。解题思路：其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
流程：
队列表示滑动窗口
头尾尾头口诀
1.头:清理超期元素(清理i-k位置的元素)2.尾:维护单调递减队列(清除队列内<新人队元素的元素)
3.尾:新元素人队
4.头:获取滑动窗口最大值(返回头部元素,i>=k-1时)
i为当前即将人队元素下标
k为滑动窗口大小
4 代码编写
4.1 暴力方式（超出时间限制）
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int m = nums.length;// 滑动次数int times = m - k + 1;int[] resultArray = new int[times];for (int i=0; i<times; i++) {int start = i;resultArray[i] = max(nums, start, k);}return resultArray;}public int max(int[] nums, int start, int k) {int maxNum = nums[start];for (int i=start; i<start+k; i++) {if (maxNum<nums[i]) {maxNum = nums[i];}}return maxNum;}
}
4.2 单调队列
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int m = nums.length;int[] result = new int[m-k+1];int resultIndex = 0;// 定义双端队列, 存储的是索引的下标Deque<Integer> deque = new LinkedList<>();for (int i=0; i<m; i++) {// 清理超期元素if (!deque.isEmpty() && deque.peek() == (i-k)) {deque.remove();}// 尾:维护单调递减队列(清除队列内<新入队元素的元素)while (!deque.isEmpty() && nums[deque.peekLast()]<=nums[i]) {deque.removeLast();}//3.尾:新元素入队deque .add(i);//4.头:获取滑动窗口最大值(返回头部元素,i>=k-1时)if (i>=k-1) {result[resultIndex++]= nums[deque.peek()];}}return result;}}