|
A major advantage of the remarkable people is: perseverance in the adverse and difficult encounter.
卓越的人的一大优点是：在不利和艰难的遭遇里百折不挠。 给定一个数组 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
提示： 1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
最简单的一种方式就是暴力求解，原理其实很简单，就是窗口在往右滑动的过程中，每滑动一步就计算窗口内最大的值，就以上面的数据画个图来看下
代码比较简单，直接看下
1public int[] maxSlidingWindow(int[] nums, int k) {
2 //边界条件判断
3 if (nums == null || nums.length == 0)
4 return new int[0];
5 int res[] = new int[nums.length - k + 1];
6 for (int i = 0; i < res.length; i++) {
7 int max = nums[i];
8 //在每个窗口内找到最大值
9 for (int j = 1; j < k; j++) {
10 max = Math.max(max, nums[i + j]);
11 }
12 res[i] = max;
13 }
14 return res;
15}
如果看过之前讲的378，数据结构-7,堆我们还可以使用堆来解决，这里可以使用最大堆，堆顶的元素是最大的，因为这题求的就是窗口内的最大值，堆的大小就是窗口的大小。因为堆的每次删除和添加都会涉及到往下调整和往上调整，所以效率一般不是很高，也可以看下，这里就是用PriorityQueue来代替堆 1public int[] maxSlidingWindow(int[] nums, int k) {
2 //边界条件的判断
3 if (nums == null || k <= 0)
4 return new int[0];
5 int[] res = new int[nums.length - k + 1];
6 int index = 0;
7 //优先队列
8 PriorityQueue<Integer> queue = new PriorityQueue<>((t1, t2) -> t2 - t1);
9 for (int i = 0; i < nums.length; i++) {
10 //元素添加到堆中
11 queue.add(nums[i]);
12 //如果堆的大小大于k，把最先加入的元素给移除
13 if (queue.size() > k)
14 queue.remove(nums[i - k]);
15 if (i >= k - 1) {
16 //把堆顶元素加入到数组中
17 res[index++] = queue.peek();
18 }
19 }
20 return res;
21}
我们知道一般的队列都是先进先出的，但双端队列两端都可以进出，如果对双端队列不熟悉的可以看下之前写的359，数据结构-3,队列。 使用双端队列首先要搞懂一个问题，就是在双端队列中，要始终保证队头是队列中最大的值。那怎么保证呢，就是在添加一个值之前，比他小的都要被移除掉，然后再添加这个值。我们举个例子，比如窗口大小是3，双端队列中依次添加3个值[4,2,5]，在添加5之前我们要把4和2给移除，让队列中只有一个5，因为窗口是往由滑动的，当添加5的时候，4和2都不可能再成为最大值了，并且4和2要比5还先出队列，搞懂了上面的过程我们随便画个图看下 搞懂了上面的过程代码就很容易写了，再看代码之前先来看一下双端队列常用的几个函数
代码如下
1public int[] maxSlidingWindow(int[] nums, int k) {
2 //边界条件的判断
3 if (nums == null || k <= 0)
4 return new int[0];
5 int[] res = new int[nums.length - k + 1];
6 int index = 0;
7 //双端队列，就是两边都可以插入和删除数据的队列，注意这里存储
8 //的是元素在数组中的下标，不是元素的值
9 Deque<Integer> qeque = new ArrayDeque<>();
10 for (int i = 0; i < nums.length; i++) {
11 //如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要
12 //出窗口了，就把队头元素给移除，注意队列中存储
13 //的是元素的下标（函数peekFirst()表示的是获取队头的下标，函数
14 //pollFirst()表示的是移除队头元素的下标）
15 if (!qeque.isEmpty() && qeque.peekFirst() <= i - k) {
16 qeque.pollFirst();
17 }
18 //在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口
19 //中队列头部元素永远是队列中最大的
20 while (!qeque.isEmpty() && nums[qeque.peekLast()] < nums[i]) {
21 qeque.pollLast();
22 }
23 //当前元素的下标加入到队列的尾部
24 qeque.addLast(i);
25 //当窗口的长度大于等于k个的时候才开始计算（注意这里的i是从0开始的）
26 if (i >= k - 1) {
27 //队头元素是队列中最大的，把队列头部的元素加入到数组中
28 res[index++] = nums[qeque.peekFirst()];
29 }
30 }
31 return res;
32}
这个不太容易想到，就是根据窗口大小把数组分成n个窗口，每个窗口分别从左往右和从右往左扫描，记录扫描的最大值，就像下面这样
窗口分好之后一个从前往后扫描一个从后往前扫描，记录每个窗口扫描的最大值。我们取窗口内的最大值的时候，如果窗口在原数组中开始的下标正好是k的倍数，比如下面这样，他的最大值很容易找
但如果窗口滑动到下面这种情况下
如果要找这个窗口的最大值，我们就要选窗口内从左边扫描最后一个和从右边扫描最后一个（窗口内从左边数第一个）的最大值，也就是下面这样
res[j] = Math.max(maxRight[i], maxLeft[i + k - 1]);
为什么要这样选，大家可以想一下，因为如果选择从左边扫描的第一个值的话，那么这个值可能不是当前窗口内的值，同理从右边扫描的也一样。 搞懂了上面的分析过程代码就很容易写了 1public int[] maxSlidingWindow(int[] nums, int k) {
2 int len = nums.length;
3 int[] maxLeft = new int[len];
4 int[] maxRight = new int[len];
5 //从左往右窗口的第一个最大值默认是数组第一个值
6 maxLeft[0] = nums[0];
7 //从右往左窗口的最后一个最大值是数组的最后一个值
8 maxRight[len - 1] = nums[len - 1];
9
10 for (int i = 1; i < len; i++) {
11 //这里分别计算从前往后窗口的最大值和从后往前窗口的最大值。要搞懂这里的判断，如果
12 //i % k == 0，表示到了下一个窗口
13 maxLeft[i] = (i % k == 0) ? nums[i] : Math.max(maxLeft[i - 1], nums[i]);
14 int j = len - i - 1;
15 maxRight[j] = ((j + 1) % k == 0) ? nums[j] : Math.max(maxRight[j + 1], nums[j]);
16 }
17 //返回的结果值
18 int[] res = new int[len - k + 1];
19 for (int i = 0, j = 0; i < res.length; i++) {
20 //取每个窗口内从左往右扫描的最后一个值和从右往左扫描的最后
21 //一个值(如果从左边数是第一个)的最大值
22 res[j++] = Math.max(maxRight[i], maxLeft[i + k - 1]);
23 }
24 return res;
25}
滑动窗口题，第一种暴力求解一般都能想到，但效率很差，最常见的就是第2种使用双端队列，第3种方式效率也挺高的，但一般不太容易想到。
|
