239. Sliding Window Maximum

我一開始看到這個, 還在想說這在侮辱我智商吧, 結果我就被打臉了

我想到O(nk)最普通的解法

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        for(int i = 0;i < nums.size() - k + 1;i++){
            int max_num = INT_MIN;
            for(int j = 0;j < k;j++){
                max_num = max(max_num, nums[i +j ]);
            }
            res.push_back(max_num);
        }
        return res;
    }
};

先記錄一個我覺得比較有照指示做得出來的

我們用一個priority_queue去紀錄一個pair, 一個紀錄數值, 另一個記錄位置,一旦發現最大的值應該要出去了, 就把他給pop掉

時間複雜度為O(n logn)

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

說真的我還真的沒用過dequeue, 真要在面試中遇到我想我應該是直接死

未完待續