题解 | #滑动窗口的最大值#

import java.util.*;
class MyPair {
    public int num;
    public int idx;
    public MyPair(int n, int i) {
        num = n;
        idx = i;
    }
    public MyPair() {
    }
}
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] nums, int size) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) {
            return ans;
        }
        if(size == 0) {
            return ans;
        } else if(size == 1) {
            for(int num : nums) {
                ans.add(num);
            }
            return ans;
        } else if(size == nums.length) {
            int max = Integer.MIN_VALUE;
            for(int num : nums) {
                if(num > max) {
                    max = num;
                }
            }
            ans.add(max);
            return ans;
        }
        LinkedList<MyPair> queue = new LinkedList<>();
        for(int i = 0; i < size; i++) {
            while(!queue.isEmpty() && (
                queue.getLast().num <= nums[i])) {
                queue.removeLast();
            }
            queue.addLast(new MyPair(nums[i], i));
//             System.out.println("queue.size = " + queue.size());
//             for(MyPair  mp : queue) {
//                 System.out.print(mp.num + " ");
//             }
//             System.out.println();
        }
        ans.add(queue.getFirst().num);
        for(int i = size, j = 0; i < nums.length; i++, j++) {
            while(!queue.isEmpty() && 
                queue.getFirst().idx <= j) {
                queue.removeFirst();
            }
            while(!queue.isEmpty() &&
                queue.getLast().num <= nums[i]) {
                queue.removeLast();
            }
            queue.addLast(new MyPair(nums[i], i));
            ans.add(queue.getFirst().num);
//             System.out.println("queue.size = " + queue.size());
//             for(MyPair  mp : queue) {
//                 System.out.print(mp.num + " ");
//             }
//             System.out.println();
        }
        return ans;
    }
}