Sliding Window Maximum
程序员文章站
2024-01-31 16:05:40
...
Sliding Window Maximum
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
return [3,3,5,5,6,7]
题目的意思是给定一个数组,一个长度为k的滑动窗口,从数组的最左边滑动到最右边,每次移动一个位置,找出每次窗口中最大的元素。这道题我们可以通过维护一个最大值的下标maxIndex,和一个最大值max来解决。遍历数组,每当窗口滑动后,我们通过最大值的下标来判断最大值元素是否还在窗口中,如果在,就只比较最大值和当前值就可以,做相应的处理;如果最大值元素不在窗口中,那我们就从这个窗口中找出最大值,时间复杂为O(k),这样总的时间复杂度为O(nk)。代码如下:
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
return [3,3,5,5,6,7]
题目的意思是给定一个数组,一个长度为k的滑动窗口,从数组的最左边滑动到最右边,每次移动一个位置,找出每次窗口中最大的元素。这道题我们可以通过维护一个最大值的下标maxIndex,和一个最大值max来解决。遍历数组,每当窗口滑动后,我们通过最大值的下标来判断最大值元素是否还在窗口中,如果在,就只比较最大值和当前值就可以,做相应的处理;如果最大值元素不在窗口中,那我们就从这个窗口中找出最大值,时间复杂为O(k),这样总的时间复杂度为O(nk)。代码如下:
public class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0) return new int[0]; if(k == 1) return nums; int maxIndex = 0; int max = Integer.MIN_VALUE; int index = 0; int[] result = new int[nums.length - k + 1]; for(int i = 0; i < nums.length - k + 1; 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; } }
上一篇: java NIO套接字编程
推荐阅读
-
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教程