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);
}
}
