给你一个整数数组 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
这个思路非常简单，先获取最大能滑动几次，然后从0开始遍历到这个数，循环中依次使用 System.arraycopy 截取数组，最后排序取出最大的数。
但是此方法耗费时间较长。
public static int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) {
return new int[0];
}
int maxOffset = nums.length - k;
int[] result = new int[maxOffset + 1];
for (int i = 0; i <= maxOffset; i++) {
int[] tag = new int[k];
System.arraycopy(nums, i, tag, 0, k);
Arrays.sort(tag);
int asInt =tag[tag.length-1];
result[i]=asInt;
}
return result;
}
public static void main(String args[]) {
int[] r = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
for (int i : r) {
System.out.println(i);
}
}
- 解法2
第二种办法就是使用一个辅助队列，从头遍历数组，更具一些规则入队或出队。
public static int[] maxSlidingWindow(int[] num, int size) {
ArrayList<Integer> result = new ArrayList<>();
if (num == null || num.length == 0 || size == 0 || size > num.length) {
return new int[0];
}
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < num.length; i++) {
if (!queue.isEmpty()) {
if (i >= queue.peek() + size) {
queue.pop();
}
while (!queue.isEmpty() && num[i] >= num[queue.getLast()]) {
queue.removeLast();
}
}
queue.offer(i);
if (i + 1 >= size) {
result.add(num[queue.peek()]);
}
}
int[] temp = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
temp[i] = result.get(i);
}
return temp;
}