給定一個陣列和滑動視窗的大小，找出所有滑動視窗里數值的最大值，例如，如果輸入陣列 {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]}，
視窗大于陣列長度的時候，回傳空
解題思路
最簡單的思路就是使用雙指標 + 優先級佇列
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.ArrayList;
public class Solution {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(3, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> list = new ArrayList<>();
if(num.length == 0 || num.length < size) {
return list;
}
int low = 0;
int high = low + size - 1;
while(high <= num.length - 1) {
for(int i = low; i <= high; i++) {
maxHeap.offer(num[i]);
}
Integer result = maxHeap.poll();
if(result != null) {
list.add(result);
}
maxHeap.clear();
low++;
high++;
}
return list;
}
}
第二種思路就是使用雙端佇列，遍歷陣列，對于每一個新加進來的元素，都先判斷是否比隊尾的元素大，這樣一來佇列頭保存的肯定就是當前滑動視窗中最大的值了，在彈出隊頭元素時，還要判斷一下元素是否過期
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
if (num == null || num.length == 0 || size <= 0 || num.length < size) {
return new ArrayList<Integer>();
}
ArrayList<Integer> result = new ArrayList<>();
// 雙端佇列，用來記錄每個視窗的最大值下標
LinkedList<Integer> qmax = new LinkedList<>();
int index = 0;
for (int i = 0; i < num.length; i++) {
while (!qmax.isEmpty() && num[qmax.peekLast()] < num[i]) {
qmax.pollLast();
}
qmax.addLast(i);
//判斷隊首元素是否過期
if (qmax.peekFirst() == i - size) {
qmax.pollFirst();
}
//向result串列中加入元素
if (i >= size - 1) {
result.add(num[qmax.peekFirst()]);
}
}
return result;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/244609.html
標籤：其他
上一篇：百度，位元組跳動，小米演算法三面感悟，（內附復習資料及答案）
下一篇：矩陣中的路徑