1、题目描述:
https://leetcode-cn.com/problems/sliding-window-maximum/
给定一个数组 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
2、思路:
使用双端队列来实现,定义两个指针,用于遍历和框定滑动窗口,li,ri,ri从数组头向后遍历,一边遍历一边向队尾插入元素的索引。
双端队列保存元素的规则:
(1)双端队列要保证从队头到队尾是单调递减。
(2)向双端队列队尾插入元素,比较待插入元素和队尾元素的大小,若待插入元素>=队尾元素,要删除队尾,直到待插入元素<队尾元素 或者 队列为空为止。
(3)校验对头元素是否失效,即队头元素在窗口之外。
(3)保存合法的队头,队头就是此时滑动窗口的最大值。
3、代码:
import java.util.Deque; import java.util.LinkedList; public class 滑动窗口的最大值 { public static void main(String[] args) { 滑动窗口的最大值 a = new 滑动窗口的最大值(); // int[] nums = {1, 3, -1, -3, 5, 3, 6, 7}; int[] nums = {1, 3, 1, 2, 0, 5}; // int[] nums = {1,-1}; // int k = 1; int k = 3; int[] result = a.maxSlidingWindow(nums, k); for (int i = 0; i < result.length; i++) { System.out.print(result[i] + ","); } } public int[] maxSlidingWindow(int[] nums, int k) { if (nums == null) { return null; } int[] result = new int[nums.length - k + 1]; Deque<Integer> deque = new LinkedList<>(); for (int ri = 0; ri < nums.length; ri++) { while (!deque.isEmpty() && nums[ri] >= nums[deque.peekLast()]) { deque.removeLast(); } deque.addLast(ri); int li = ri - k + 1; if (li < 0) continue; if (li > deque.peekFirst()) { deque.removeFirst(); } result[li] = nums[deque.peekFirst()]; } return result; } }
。。。。