題目描述
給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數(shù)組{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]}。
算法解析： 這個算法利用雙端隊列實現(xiàn)，我們拿上邊這個數(shù)組舉例子，首先先塞滿整個窗口，即我們首先先遍歷到滿足窗口大小的位置，然后將最可能稱為最大值的放到隊列的頭，也就是說當(dāng)我們遍歷到一個數(shù)組值的時候，如果隊頭的值小于當(dāng)前值，我們移除隊頭，隊尾值小于當(dāng)前值，我們移除隊尾，隊列頭永遠(yuǎn)存放當(dāng)前滑動窗口的最大值。
代碼如下：
public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> result = new ArrayList<>(); if (num.length >= size && size >= 1){ Deque<Integer> doubleQueue = new ArrayDeque<>(); for (int i = 0; i < size; i++) { while (!doubleQueue.isEmpty() && num[i] >= num[doubleQueue.peekFirst()]){ doubleQueue.pollFirst(); } while (!doubleQueue.isEmpty() && num[i] >= num[doubleQueue.peekLast()]){ doubleQueue.pollLast(); } doubleQueue.addLast(i); } for (int i = size; i < num.length; i++) { result.add(num[doubleQueue.peekFirst()]); while (!doubleQueue.isEmpty() && num[i] >= num[doubleQueue.peekFirst()]){ doubleQueue.pollFirst(); } while (!doubleQueue.isEmpty() && num[i] >= num[doubleQueue.peekLast()]){ doubleQueue.pollLast(); } if (!doubleQueue.isEmpty() && doubleQueue.peekFirst() <= (i - size)){ doubleQueue.pollFirst(); } doubleQueue.addLast(i); } result.add(num[doubleQueue.peekFirst()]); } return result; }新聞熱點(diǎn)
疑難解答
