Java?C++分別實現滑動窗口的最大值
1、題目
給定一個數組 nums 和滑動窗口的大小 k,請找出所有滑動窗口里的最大值。
示例:

提示:
你可以假設 k 總是有效的,在輸入數組不為空的情況下,1 ≤ k ≤ 輸入數組的大小。
2、思路
(單調隊列) O(n)
給定一個數組 nums 和滑動窗口的大小 k,讓我們找出所有滑動窗口里的最大值。
樣例:

如樣例所示,nums = [1,3,-1,-3,5,3,6,7],k = 3,我們輸出[3,3,5,5,6,7]。
首先,我們可以想到最樸素的做法是模擬滑動窗口的過程,每向右滑動一次都遍歷一遍滑動窗口,找到最大的元素輸出,這樣的時間復雜度是O ( n k ) O(nk)O(nk)??紤]優(yōu)化,其實滑動窗口類似于數據結構雙端隊列,窗口向右滑動過程相當于向隊尾添加新的元素,同時再把隊首元素刪除。

如何更快的找到隊列中的最大值?
其實我們可以發(fā)現,隊列中沒必要維護窗口中的所有元素,我們可以在隊列中只保留那些可能成為窗口中的最大元素,去掉那些不可能成為窗口中的最大元素。
考慮這樣一種情況,如果新進來的數字大于滑動窗口的末尾元素,那么末尾元素就不可能再成為窗口中最大的元素了,因為這個大的數字是后進來的,一定會比之前先進入窗口的小的數字要晚離開窗口,因此我們就可以將滑動窗口中比其小的數字彈出隊列,于是隊列中的元素就會維持從隊頭到隊尾單調遞減,這就是單調遞減隊列。
單調遞增隊列

對于隊列內的元素來說:
- 在隊列內自己左邊的數就是數組中左邊第一個比自己小的元素。
- 當被彈出時,遇到的就是數組中右邊第一個比自己小的元素 。( 只要元素還在隊列中,就意味著暫時還沒有數組中找到自己右側比自己小的元素)
- 隊頭到隊尾單調遞增,隊首元素為隊列最小值。
單調遞減隊列

對于隊列內的元素來說:
- 在隊列內自己左邊的數就是數組中左邊第一個比自己大的元素。
- 當被彈出時,遇到的就是數組中右邊第一個比自己大的元素 ,只要元素還在隊列中,就意味著暫時還沒有數組中找到自己右側比自己大的元素。
- 隊頭到隊尾單調遞減,隊首元素為隊列最大值。
了解了單調隊列的一些性質以后,對于這道題我們就可以維護一個單調遞減隊列,來保存隊列中所有遞減的元素 ,隨著入隊和出隊操作實時更新隊列,這樣隊首元素始終就是隊列中的最大值。同時如果隊首元素在滑動窗口中,我們就可以將其加入答案數組中。
實現細節(jié):
為了方便判斷隊首元素與滑動窗口的位置關系,隊列中保存的是對應元素的下標。
具體解題過程如下:
初始時單調隊列為空,隨著對數組的遍歷過程中,每次插入元素前,需要考察兩個事情:
1、合法性檢查:隊頭下標如果距離i 超過了 k ,則應該出隊。
2、單調性維護:如果 nums[i] 大于或等于隊尾元素下標所對應的值,則當前隊尾再也不可能充當某個滑動窗口的最大值了,故需要隊尾出隊,始終保持隊中元素從隊頭到隊尾單調遞減。
3、如次遍歷一遍數組,隊頭就是每個滑動窗口的最大值所在下標。
時間復雜度分析: 每個元素最多入隊出隊一次,復雜度為O ( n ) O(n)O(n)。
3、c++代碼
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int>q; //雙端隊列
vector<int>res;
for(int i = 0; i < nums.size(); i++){
while(q.size() && i - k + 1 > q.front()) q.pop_front(); //判斷隊頭是否在滑動窗口范圍內
while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();//維護單調遞減隊列
q.push_back(i); //將當前元素插入隊尾
if(i >= k - 1) res.push_back(nums[q.front()]); //滑動窗口的元素達到了k個,才可以將其加入答案數組中
}
return res;
}
};
4、java代碼
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> queue = new ArrayDeque<>(); //雙端隊列
int[] res = new int[n - k + 1];
for (int i = 0 , j = 0; i < n; i++) {
//判斷隊頭是否在滑動窗口范圍內
while (!queue.isEmpty() && i- k + 1 > queue.getFirst()) queue.pollFirst();
//維護單調遞減隊列
while (!queue.isEmpty() && nums[i] > nums[queue.getLast()]) queue.pollLast();
queue.offer(i); //將當前元素插入隊尾
//滑動窗口的元素達到了k個,才可以將其加入答案數組中
if( i - k + 1 >= 0) res[j++] = nums[queue.getFirst()];
}
return res;
}
}
以上就是Java C++分別實現滑動窗口的最大值的詳細內容,更多關于Java C++ 滑動窗口最大值的資料請關注腳本之家其它相關文章!
相關文章
解決IDEA2020.1.2IDEA打不開的問題(最新分享)
由于idea安裝多了某個jar,點擊出現讀條后閃退情況,接下來通過本文給大家分享解決IDEA2020.1.2IDEA打不開的問題,非常不錯,具有一定的參考借鑒價值,感興趣的朋友跟隨小編一起看看吧2020-07-07
Spring?Boot監(jiān)控SQL運行情況的全過程
這篇文章主要給大家介紹了關于Spring?Boot監(jiān)控SQL運行情況的相關資料,文中通過實例代碼介紹的非常詳細,對大家學習或者使用SpringBoot具有一定的參考學習價值,需要的朋友可以參考下2022-02-02

