【剑指Offer】滑动窗口的最大值（笔试&面试解法）

 1 class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if(nums == null || nums.length == 0){
 4             return new int[nums.length];
 5         }
 6         int[] ans = new int[nums.length-k+1];
 7         for(int i = 0; i < nums.length-k+1; i++){
 8             int max = Integer.MIN_VALUE;
 9             for(int j = i; j < i+k; j++){
10                 max = Math.max(max,nums[j]);
11             }
12             ans[i] = max;
13         }
14         return ans;
15     }
16 }

 1 class Solution {
 2     public int[] maxSlidingWindow(int[] nums, int k) {
 3         if(nums == null || nums.length == 0){
 4             return new int[nums.length];
 5         }
 6         LinkedList<Integer> maxQueue = new LinkedList<>();
 7         int[] ans = new int[nums.length-k+1];
 8         int index = 0;
 9         for(int i = 0; i < nums.length; i++){
10             //队尾元素小于数组元素 立即弹出 始终保持队头元素最大
11             while(!maxQueue.isEmpty() && nums[maxQueue.peekLast()]<nums[i]){
12                 maxQueue.pollLast();
13             }
14             //队尾元素较大 则加入队列做跟班
15             maxQueue.add(i);
16             //判断队头元素是否过期 过期则弹出
17             if(maxQueue.peekFirst() == i-k){
18                 maxQueue.pollFirst();
19             }
20             if(i >= k-1){
21                 ans[index++] = nums[maxQueue.peekFirst()];
22             }
23         }
24         return ans;
25     }
26 }