Sliding Window Maximum
程序员文章站
2024-01-31 16:05:34
...
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[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
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
滑动窗口的题目,我们可以借助双向队列deque来解决。一边维护窗口的大小,一边将每个窗口的中的最大元素放在队列的头部,这样每次取队列的第一个元素就可以了。代码如下:
如果不用队列也可以,思路是一样的,维护一个窗口,当窗口移动之后,检查之前窗口的最大元素是否在移动后的窗口中,如果在只需要比较最大元素与新近的元素就可以;如果不存在就在新窗口中找最大元素。代码如下:
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[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
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
滑动窗口的题目,我们可以借助双向队列deque来解决。一边维护窗口的大小,一边将每个窗口的中的最大元素放在队列的头部,这样每次取队列的第一个元素就可以了。代码如下:
public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; int[] result = new int[nums.length - k + 1]; Deque<Integer> deque = new LinkedList<Integer>(); int index = 0; for(int i = 0; i < nums.length; i++) { //查看之前的最大元素是否在窗口中,如果不在就删除 if(!deque.isEmpty() && (deque.getFirst() == (i - k))) deque.removeFirst(); //添加新的元素到队尾 while(!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) deque.removeLast(); deque.addLast(i); //将最大元素加入到结果中 if(i >= k - 1) result[index ++] = nums[deque.getFirst()]; } return result; } }
如果不用队列也可以,思路是一样的,维护一个窗口,当窗口移动之后,检查之前窗口的最大元素是否在移动后的窗口中,如果在只需要比较最大元素与新近的元素就可以;如果不存在就在新窗口中找最大元素。代码如下:
public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; int[] result = new int[nums.length - k + 1]; int maxIndex = 0; int max = Integer.MIN_VALUE; int index = 0; for(int i = 0; i < result.length; i++) { if(i == 0 || maxIndex == i - 1) { max = Integer.MIN_VALUE; for(int j = i; j < i + k; j++) if(nums[j] > max) { max = nums[j]; maxIndex = j; } }else { if(nums[i + k - 1] > max) { max = nums[i + k - 1]; maxIndex = i + k - 1; } } result[index ++] = max; } return result; } }
下一篇: 初识SPDY协议
推荐阅读
-
Sliding Window Maximum
-
Sliding Window Maximum
-
window php imagick 保存图片不成功
-
php在window下的安装
-
PHP 4.04 在window/nt/2000下各种服务器的安装方法(1)
-
phpstorm the jvm could not be started the maximum heap size…
-
WPF自定义Window窗体样式
-
Window 下安装Mysql5.7.17 及设置编码为utf8的方法
-
Linux tomcat连接Window MySQL异常的解决
-
php实现window平台的checkdnsrr函数,windowcheckdnsrr_PHP教程