class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int[] res = new int[len - k + 1];
for (int i = 0; i < len - k + 1; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i+k; j++) {
if (max < nums[j]) {
max = nums[j];
}
}
res[i] = max;
}
return res;
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int[] res = new int[len - k + 1];
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < len; i++) {
// 维护一个单调递增队列,使队列中的元素递减
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
queue.pollLast();
}
// 下一个新窗口的元素下标入队
queue.offer(i);
// 判断此时最大值是不是在窗口的有效范围中
if (queue.peek() <= i-k) {
queue.poll();
}
// 当i >= k-1 才开始计算结果
if (i >= k-1) {
res[i-k+1] = nums[queue.peek()];
}
}
return res;
}
}
原文:https://www.cnblogs.com/linzedian/p/14065693.html