239
Sliding Window Maximum
22.1%
Hard
優(yōu)先級隊(duì)列 nlogn 不是線性時間
提示1 用鏈表。 每次移動 ＝ 加入元素 ＋ 刪除元素
在這兩步操作上思考
加入元素可以優(yōu)化
如果新加入元素，比之前元素大迁酸，那么之前元素沒用了（因?yàn)楸刃略叵缺粍h除）讲冠，可以刪除瓜客。
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);
}
}
