My code:
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
int[] ret = new int[0];
return ret;
}
int[] ret = new int[nums.length - k + 1];
int pre = -1;
for (int i = 0; i <= nums.length - k; i++) {
if (pre < i) {
if (pre >= 0 && nums[i + k - 1] >= nums[pre]) {
pre = i + k - 1;
ret[i] = nums[pre];
}
else {
int max = i;
for (int j = i + 1; j < i + k; j++) {
if (nums[j] >= nums[max]) {
max = j;
}
}
pre = max;
ret[i] = nums[pre];
}
}
else {
if (nums[i + k - 1] >= nums[pre]) {
pre = i + k - 1;
}
ret[i] = nums[pre];
}
}
return ret;
}
}
我自己的解法比较单纯，没用什么额外的数据结构。
就是维持一个指针指向上一层的最大数的index。如果有多个数最大且相等，这个index选他们之中最大的index
然后逻辑比较简单。
如果这个指针在当前范围之外，那么这个数就不用在考虑了。
此时，如果新加进来的数比他更大，那么直接更新指针。
如果小，那么就得遍历当前范围，找出最大的那个值，更新指针。
如果在范围之内，那么就和新加进来的数比较一下，更新指针。
然后看到了用 Deque 的解法。自己写了下。
My code:
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
int[] ret = new int[0];
return ret;
}
int[] ret = new int[nums.length - k + 1];
Deque<Integer> q = new ArrayDeque<Integer>();
int counter = 0;
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && q.peek() < i - k + 1) {
q.poll();
}
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
q.pollLast();
}
q.offerLast(i);
if (i >= k - 1) {
ret[counter] = nums[q.peek()];
counter++;
}
}
return ret;
}
}
reference:
https://discuss.leetcode.com/topic/19055/java-o-n-solution-using-deque-with-explanation/2
对Deque的API不是很熟悉。
参考：
https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html
他的思想就是类似于一种插入排序，从大到下。只不过把尾部（右侧）比自己小的都删除了。然后每次最大的值都在头部（左侧）。
同时每次都得把不在范围内的index都删除掉。
差不多就这样了。
q.pollFirst(), 对应最左侧
q.pollLast(), 对应最右侧
Anyway, Good luck, Richardo! -- 09/03/2016
