239 Sliding Window Maximum

239
Sliding Window Maximum
22.1%
Hard

优先级队列 nlogn 不是线性时间
提示1 用链表。 每次移动 ＝ 加入元素 ＋ 删除元素
在这两步操作上思考
加入元素可以优化
如果新加入元素，比之前元素大，那么之前元素没用了（因为比新元素先被删除），可以删除。

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        LinkedList<Integer> valList = new LinkedList<Integer>();
        LinkedList<Integer> indexList = new LinkedList<Integer>();
        int[] rst = new int[nums.length - k + 1];
        for (int i = 0; i<k ; i++)
            addNumber(valList, indexList, nums[i], i);
        rst[0] = valList.peekFirst();
        for (int i=k; i<nums.length; i++){
            // add [i], remove [i-k]
            addNumber(valList, indexList, nums[i], i);
            if (indexList.peekFirst() == i-k){
                valList.pollFirst();
                indexList.pollFirst();
            }
            rst[i-k+1] = valList.peekFirst();
        }
        return rst;
    }
    private void addNumber(LinkedList<Integer> valList, LinkedList<Integer> indexList, int val, int index){
        while (!valList.isEmpty() && valList.peekLast()<=val){
            valList.pollLast();
            indexList.pollLast();
        }
        valList.addLast(val);
        indexList.addLast(index);
    }
}