Leetcode刷题之 【剑指 Offer 59 - I. 滑动窗口的最大值】

1 题目

给定一个数组 nums 和滑动窗口的大小 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 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 Java代码

（1）暴力求解

//暴力求解 public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] res = {}; if (n == 0) return res; if (k > n) return res; if (k==1) return nums; res = new int[n - k + 1]; for (int i = 0; i <= n - k; i++) { res[i] = nums[i]; for (int j = 1; j < k; j++) { if (res[i] < nums[i + j]) { res[i] = nums[i + j]; } } } return res; }

（2）使用单调队列

public int[] maxSlidingWindow3(int[] nums, int k) { int n = nums.length; int[] res = {}; if (n == 0 || k==0 || k>n) return res; if (k == 1) return nums; res = new int[n - k + 1]; Deque<Integer> deque = new LinkedList<>(); for (int i = 0; i < k; i++) { //形成窗口前 while (!deque.isEmpty() && nums[i] > deque.peekLast()) { deque.removeLast(); } deque.addLast(nums[i]); } res[0] = deque.peekFirst(); //将当前队列中的最大元素添加到结果数组中 for (int i = k; i < n; i++) { //对之后的数据再次循环 if (deque.peekFirst() == nums[i - k]) deque.removeFirst(); while (!deque.isEmpty() && nums[i] > deque.peekLast()) deque.removeLast(); deque.addLast(nums[i]); res[i - k + 1] = deque.peekFirst(); } return res; }

3 完整代码

import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; public class MaxSlidingWindow { public static void main(String[] args) { MaxSlidingWindow maxSlidingWindow = new MaxSlidingWindow(); int[] nums = {1, 3, 1, 2, 0, 5}; int k = 3; int[] res = maxSlidingWindow.maxSlidingWindow(nums, k); System.out.println(Arrays.toString(res)); int[] res3 = maxSlidingWindow.maxSlidingWindow3(nums, k); System.out.println(Arrays.toString(res3)); } //暴力破解 public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] res = {}; if (n == 0) return res; if (k > n) return res; if (k == 1) return nums; res = new int[n - k + 1]; for (int i = 0; i <= n - k; i++) { res[i] = nums[i]; for (int j = 1; j < k; j++) { if (res[i] < nums[i + j]) { res[i] = nums[i + j]; } } } return res; } //双端队列实现 public int[] maxSlidingWindow3(int[] nums, int k) { int n = nums.length; int[] res = {}; if (n == 0 || k==0 || k>n) return res; if (k == 1) return nums; res = new int[n - k + 1]; Deque<Integer> deque = new LinkedList<>(); for (int i = 0; i < k; i++) { //形成窗口前 while (!deque.isEmpty() && nums[i] > deque.peekLast()) { deque.removeLast(); } deque.addLast(nums[i]); } res[0] = deque.peekFirst(); //将当前队列中的最大元素添加到结果数组中 for (int i = k; i < n; i++) { //对之后的数据再次循环 if (deque.peekFirst() == nums[i - k]) deque.removeFirst(); while (!deque.isEmpty() && nums[i] > deque.peekLast()) deque.removeLast(); deque.addLast(nums[i]); res[i - k + 1] = deque.peekFirst(); } return res; } }