剑指 Offer 59 - I. 滑动窗口的最大值
题目
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
解法
class Solution {
public int[] maxSlidingWindow(int[] nums
, int k
) {
if(nums
.length
== 0 || k
== 0) return new int[0];
Deque
<Integer> dq
= new LinkedList<>();
int len
= nums
.length
;
int[] res
= new int[len
-k
+1];
for(int i
= 0 ; i
< k
; ++i
){
int cur
= nums
[i
];
while(!dq
.isEmpty()&&dq
.peekLast()<cur
) dq
.removeLast();
dq
.addLast(cur
);
}
res
[0] = dq
.peekFirst();
for(int i
= k
; i
< len
; ++i
){
int cur
= nums
[i
];
if(nums
[i
-k
]==dq
.peekFirst()) dq
.removeFirst();
while(!dq
.isEmpty()&&dq
.peekLast()<cur
) dq
.removeLast();
dq
.addLast(cur
);
res
[i
-k
+1] = dq
.peekFirst();
}
return res
;
}
}
