Q239SlidingWindowMaximum
簡介
給你一個整數陣列 nums ，有一個大小為 k 的滑動視窗從陣列的最左側移動到陣列的最右側，你只可以看到在滑動視窗內的 k 個數字，滑動視窗每次只向右移動一位，
回傳 滑動視窗中的最大值 ，
示例 1：
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
| 滑動視窗的位置 | 最大值 |
|---|---|
| [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 |
示例 2：
輸入：nums = [1], k = 1
輸出：[1]
https://leetcode.cn/problems/sliding-window-maximum
解題
優先佇列
考慮到題目要求是取一段內容里的最大值，可以考慮優先佇列，即按一定順序排列的佇列，將區間內數字放到佇列中，隊頭即區間最大值，在滑動視窗時不斷移除不在區間內的元素，添加新的元素即可，但這種方法會超時，問題就出現在移除佇列的時候，最壞的時間復雜度有 O(N2logn)，要考慮更低時間復雜度的方法，
主要優化洗掉時候的耗時，像前面提到的洗掉方法是每走一步便要洗掉一次，而且是遍歷洗掉，要想到當隊首元素（最大的元素）不需要被洗掉時，其余元素也可不洗掉，因為總有元素比它大，只有當隊首元素移動到區間左側的時候，才需要洗掉，此時也可從隊首開始洗掉，不需要遍歷洗掉，不斷移除隊首元素直到隊首元素確切的在區間中即可，
由于需要判斷隊首元素是否在區間外，需要在佇列的元素中添加元素位置，構成<元素， 元素位置> 這樣一個二元組放到優先佇列里面，
時間復雜度為 O(nlogn)
代碼如下
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> o2[0] - o1[0])); //佇列按降序排序
int len = nums.length;
int i = 0;
while (i < k){ //佇列初始化
queue.add(new int[]{nums[i], i});
i++;
}
int[] rtn = new int[len - k + 1];
rtn[0] = queue.peek()[0];
while (i < len){
queue.add(new int[]{nums[i], i}); //保證佇列不空
while (queue.peek()[1] <= i - k) { //當隊首元素不在區間范圍內是，不斷洗掉隊首元素直到符合標準
queue.poll();
}
rtn[i-k+1]=queue.peek()[0];
i++;
}
return rtn;
}
提交結果
單調佇列
單調佇列是對上面方法的優化，使用雙端佇列，對隊頭和隊尾操作，時間比優先佇列（大小根堆）要快一點，
- 佇列中依然是從大到小排列
- 每移動一步，將新值與隊尾元素比較，不斷出隊到佇列慷訓新值小于隊尾元素，此時就可出隊是因為新值在佇列原有元素右側，一定會晚于元素元素出隊，故原有元素可以洗掉，
- 移除不在區間的元素，可將元素與隊首元素比較，如果相同則移除隊首元素，不同可不做處理，因為如果要移除的元素是剩余區間最大的且比隊首元素小，那么在隊首元素插入的時候要移除的元素已經被移除了，不會再佇列中存在
代碼
public class Q239SlidingWindowMaximum {
static class MyQueue{ //封裝一個新類，也可寫入主代碼里面
Deque<Integer> queue = new LinkedList<>();
void push(int val){ // 插入操作
while(!queue.isEmpty() && val > queue.getLast()){
queue.removeLast();
}
queue.addLast(val);
}
void poll(int val){ //移除操作
if (!queue.isEmpty() && val == queue.getFirst()){
queue.removeFirst();
}
}
int peek(){ //取隊首
return queue.getFirst();
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1 || k == 1){
return nums;
}
MyQueue queue = new MyQueue();
int len = nums.length - k + 1;
int[] rtn = new int[len];
int num = 0;
for (int i = 0; i < k; i++) {
queue.push(nums[i]);
}
rtn[num++] = queue.peek();
for (int i = k; i < nums.length; i++) {
queue.poll(nums[i - k]);
queue.push(nums[i]);
rtn[num++] = queue.peek();
}
return rtn;
}
}
提交結果
可看到時間較前一方法有所縮短
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501625.html
標籤：其他
上一篇：「題解報告」 P3167 [CQOI2014]通配符匹配
下一篇：SOAP 和 REST 的區別