[LeetCode][Hard] 239. Sliding Window Maximum

Leetcode 網址: https://leetcode.com/problems/sliding-window-maximum/

題目說明:

給定一個沒有排列長度為 n 的陣列與窗口大小 k ( 1 <=k <= n)，

每次窗口會往右移動一格，直到窗口大小超出陣列長度，

請找出移動過程中窗口範圍內的最大值。

解題說明:

這題最暴力法直接做就是每次從大小為 k 窗口中找最大元素，

由於 n 可能等於 n / 2，所以暴力法的時間複雜度為 O (n^2)。

接著再來思考比較好的做法就是 Max Heap，

Max Heap 插入跟刪除的時間複雜度皆為 O (log n)，

由於插入跟刪除最多為 n 次，所以其時間複雜度可以壓到 O (n log n) ~

後來解完題目後，看了下討論區有種 O (n) 的解法是用 double-ended queue，

其算法概念是每次新增元素到 queue 前，把那些沒有用的元素先 pop 掉，

例如: 4 3 2 1 7 來說，當我們要新增 7 的時候就把前面的 pop 掉，

原因是往右邊移動的話， 4 3 2 1 這幾個數字絕對不可能是最大值， 

所以有以上想法後就可以解決此題啦!

程式碼 (Max Heap)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < nums.size(); i++) {
            while (i >= k && pq.size() > 0 && i - k >= pq.top().second) pq.pop();
            pq.push(pair(nums[i], i));
            if (i >= k - 1) result.push_back(pq.top().first);
            
        }
        return result;
    }
};

程式碼 (Double-ended queue)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && i - k == dq.front()) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) result.push_back(nums[dq.front()]);      
        }
        return result;
    }
};

結果

Runtime: 216 ms, faster than 98.61% of C++ online submissions for Sliding Window Maximum.

Memory Usage: 118.7 MB, less than 52.05% of C++ online submissions for Sliding Window Maximum.