描述

滑动窗口最大值239

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.Deque;
import java.util.LinkedList;

//239. 滑动窗口最大值
public class SlidingWindowMaximum239 {
	public static void main(String[] args){
		int[] arr = {1,3,-1,-3,3,3,6,7};
		int k = 3;
		for (int item : new Solution().maxSlidingWindow(arr,k)) {
			System.out.print(item + "\t");
		}
	}
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
    	if (nums.length == 1){
    		return nums;
    	}
    	MyQueue myQueue = new MyQueue();
    	int len = nums.length - k + 1;
    	int[] res = new int[len];
    	int temp = 0;

    	//先进k个队列
    	for (int i = 0; i < k; i++) {
    		myQueue.add(nums[i]);
    	}
    	res[temp++] = myQueue.peek();

    	for (int j = k; j < nums.length; j++) {
    		myQueue.poll(nums[j - k]);
    		myQueue.add(nums[j]);
    		res[temp++] = myQueue.peek();
    	}
    	return res;


    }
}

class MyQueue {
	Deque<Integer> deque = new LinkedList<>();

	//poll
	void poll(int num){
		if (!deque.isEmpty() && deque.peek() == num) {
			deque.poll();
		}
	}
	//add
	void add(int num){
		while(!deque.isEmpty() && num > deque.getLast()) deque.removeLast();
		deque.add(num);
	}
	//peek
	int peek(){
		return deque.peek();
	} 
}

总结

主要是一个思想，你领悟到了没有？

队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

单调队列，即单调递减或单调递增的队列。