題目描述
給定一個陣列和滑動視窗的大小，找出所有滑動視窗里數值的最大值，例如，如果輸入陣列{2,3,4,2,6,2,5,1}及滑動視窗的大小3，那么一共存在6個滑動視窗，他們的最大值分別為{4,4,6,6,6,5}； 針對陣列{2,3,4,2,6,2,5,1}的滑動視窗有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}，
思路
使用LinkedList作為雙端佇列存盤視窗最大值的陣列下標，佇列增刪規則如下： 向佇列添加元素前，將隊尾小于該元素的值依次洗掉，將隊頭中已離開當前視窗的下標元素洗掉， 每一輪添加元素時，當前隊頭保存的即視窗最大值的下標， 使用ArrayList保存每一輪視窗的最大值，時間復雜度O(n)，空間復雜度O(n)，
代碼
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> ans = new ArrayList<>();
if(num == null || num.length == 0 || size < 1) {
return ans;
}
LinkedList<Integer> list = new LinkedList<>();
for(int i = 0; i < num.length; i++) {
while(!list.isEmpty() && num[list.getLast()] < num[i]) {
list.removeLast();
} // 將小于當前元素的結點從隊尾洗掉
while(!list.isEmpty() && i - list.getFirst() + 1 > size) {
list.removeFirst();
} // 將已經離開視窗的元素從隊頭洗掉
list.add(i);
if(i + 1 >= size) {
ans.add(num[list.getFirst()]);
}
}
return ans;
}
}
筆記
無
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57199.html
標籤：其他
上一篇：資料結構（C語言版）---二叉樹
下一篇：回圈佇列-雙端和單端