題目：

鏈接：劍指 Offer 59 - I. 滑動(dòng)窗口的最大值；LeetCode 239. 滑動(dòng)窗口最大值
難度：困難
下一篇：劍指 Offer 59 - II. 隊(duì)列的最大值（單調(diào)隊(duì)列）

給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。

返回 滑動(dòng)窗口中的最大值 。

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋?zhuān)?br> 滑動(dòng)窗口的位置????最大值
---------------------?????-----
[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]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

方法一：

優(yōu)先隊(duì)列（不推薦）：

優(yōu)先隊(duì)列的本質(zhì)是最大堆，可以幫助實(shí)時(shí)維護(hù)一個(gè)滑動(dòng)窗口中的最大值。
初始時(shí)，將數(shù)組nums前k個(gè)元素插入優(yōu)先隊(duì)列中。每當(dāng)右移窗口時(shí)，就將新的元素插入優(yōu)先隊(duì)列（最大堆），那么此時(shí)堆頂?shù)脑鼐褪亲畲笾?。然而這個(gè)最大值有可能經(jīng)過(guò)右移已不在窗口中（在窗口左邊界的更左位置），所以我們要根據(jù)這個(gè)棧頂元素的實(shí)際坐標(biāo)移除已不在窗口中的堆頂元素，直到堆頂元素確實(shí)在窗口范圍中，此時(shí)的堆頂元素才是窗口內(nèi)的最大值。
為了方便判斷堆頂元素與滑動(dòng)窗口的位置關(guān)系，我們可以在優(yōu)先隊(duì)列中存儲(chǔ)二元組 (num,index)，表示元素 num 在數(shù)組中的下標(biāo)為 index。優(yōu)先隊(duì)列會(huì)默認(rèn)按第一個(gè)整數(shù)進(jìn)行優(yōu)先級(jí)排序。

代碼一：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0) return {};
        priority_queue<pair<int, int>> window;  // 維護(hù)一個(gè)滑動(dòng)窗口內(nèi)的優(yōu)先隊(duì)列
        vector<int> ans;
        for(int i = 0; i < k; i++)
        {
            window.emplace(nums[i], i);
        }
        ans.emplace_back(window.top().first);
        for(int i = k; i < n; i++)
        {
            window.emplace(nums[i], i);
            while(window.top().second <= i - k) {  // 將滑動(dòng)窗口外的元素刪掉
                window.pop();
            }
            ans.emplace_back(window.top().first);
        }
        return ans;
    }
};

時(shí)間復(fù)雜度O(NlogN)。在最壞情況下，nums數(shù)組呈單調(diào)遞增，優(yōu)先隊(duì)列中插入了所有元素且沒(méi)有元素被刪除，將一個(gè)元素插入優(yōu)先隊(duì)列的時(shí)間復(fù)雜度為O(logN)，n個(gè)元素為O(NlogN)。
空間復(fù)雜度O(N)。在上述的最壞情況下，優(yōu)先隊(duì)列需要n個(gè)元素的空間。

方法二：

單調(diào)隊(duì)列（推薦）：

使用雙端隊(duì)列deque實(shí)現(xiàn)的單調(diào)隊(duì)列詳解看單調(diào)隊(duì)列結(jié)構(gòu)解決滑動(dòng)窗口問(wèn)題。
順著方法一的思路進(jìn)行優(yōu)化，方法一中優(yōu)先隊(duì)列在發(fā)現(xiàn)堆頂元素在窗口外之前仍保留窗口外元素的特點(diǎn)是冗余的。我們可以發(fā)現(xiàn)，若滑動(dòng)窗口中有兩個(gè)下標(biāo) i < j，nums[i] <= nums[j]，只要 i 還在窗口中，j 一定也在窗口中，nums[i] 就一定不是窗口最大值了，所以 nums[i] 可以被永久移除。這符合單調(diào)隊(duì)列的性質(zhì)。

代碼二：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0) return {};
        deque<int> window;  //單調(diào)遞減隊(duì)列
        vector<int> ans;
        for(int i = 0; i < n; i++)
        {
            while(!window.empty() && window.back() < nums[i]) {  //維護(hù)一個(gè)單調(diào)遞減隊(duì)列，把單調(diào)隊(duì)列中比新元素小的元素全部刪除
                window.pop_back();
            }
            window.emplace_back(nums[i]);
            if(i == k - 1) {
                ans.emplace_back(window.front());
            }
            else if(i >= k) {
                if(window.front() == nums[i - k]) window.pop_front();  //維護(hù)一個(gè)單調(diào)遞減隊(duì)列，刪除滑動(dòng)窗口右移丟失的最大值
                ans.emplace_back(window.front());
            }
        }
        return ans;
    }
};

時(shí)間復(fù)雜度O(N)。
空間復(fù)雜度O(k)。窗口右移時(shí)從隊(duì)首彈出元素保證了隊(duì)列內(nèi)不會(huì)有超過(guò) k+1 個(gè)元素。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-605632.html

到了這里，關(guān)于劍指 Offer 59 - I. 滑動(dòng)窗口的最大值 / LeetCode 239. 滑動(dòng)窗口最大值（優(yōu)先隊(duì)列 / 單調(diào)隊(duì)列）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！