239. Sliding Window Maximum

解題思路

看 neetcode 的方法來解這題。

btw 問了 chatGPT 發現我寫的程式碼還是太醜了XD

程式碼

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