給定一個(gè)數(shù)組 nums睹耐，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口 k 內(nèi)的數(shù)字括享÷Ц滑動(dòng)窗口每次只向右移動(dòng)一位。
返回滑動(dòng)窗口最大值奶浦。
示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動(dòng)窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
注意：
你可以假設(shè) k 總是有效的兄墅，1 ≤ k ≤ 輸入數(shù)組的大小，且輸入數(shù)組不為空澳叉。
思路
定義一個(gè)雙端隊(duì)列MyDeque類隙咸，將這隊(duì)列作為滑動(dòng)窗口，先向隊(duì)列填窗口前k-1個(gè)數(shù)成洗，push方法每添加一個(gè)數(shù)會(huì)先判斷五督，后添加的數(shù)如果大于之前添加，會(huì)將之前添加的數(shù)刪除瓶殃，可以認(rèn)為后來(lái)的數(shù)壓扁錢前面的數(shù)充包，則當(dāng)前組的最大值就是隊(duì)頭，往下滑動(dòng)遥椿，要?jiǎng)h除窗口的第一個(gè)數(shù)基矮，這里需要判斷，這第一個(gè)數(shù)可能已經(jīng)后來(lái)的數(shù)壓扁冠场，如果沒(méi)有壓扁家浇，則需要?jiǎng)h除(因?yàn)榛瑒?dòng)窗口向右滑動(dòng)，前面刪除一個(gè)數(shù)碴裙，后面增加一個(gè)數(shù))
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MyDeque myDeque = new MyDeque();
int res[] = {};
if (nums == null || nums.length == 0) {
return res;
} else {
res = new int[nums.length - k + 1];
}
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
myDeque.push(nums[i]);
} else {
myDeque.push(nums[i]);
res[j++] = myDeque.max();
myDeque.pop(nums[i - k + 1]);
}
}
return res;
}
class MyDeque {
private Deque<Integer> deque;
public MyDeque() {
deque = new LinkedList<Integer>();
}
void push(int n) {
while ((!deque.isEmpty()) && deque.getLast() < n) {
deque.removeLast();
}
deque.addLast(n);
}
void pop(int n) {
if ((!deque.isEmpty()) && deque.getFirst() == n) {
deque.removeFirst();
}
}
int max() {
return deque.getFirst();
}
}
