LeetCode 239：滑動視窗最大值

方法一：暴力法 ，時間複雜度O((n-k) * k)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty() || k<=1) return nums; 

        vector<int> subMax(nums.size()-k+1);

        int i = 0;
        for(int j = k-1; j < nums.size(); j++) {
            int temp = nums[i];
            for (int l = i+1; l <= j; l++) {
                if(temp < nums[l]) temp = nums[l];
            }
            subMax[i] = temp;
            i++;
        }

        return subMax;
    }
};
           

方法二：

 采用單調隊列作為輔助資料結構，每移動一次，就是在一堆數中去掉一個元素，再加一個元素。需要及時更新隊頭，删除出窗的元素索引，隊尾元素單調入隊，就是比它小的先彈出去再讓它入隊。這樣隊頭始終保持最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty() || k<=1) return nums; 

        vector<int> result;
        deque<int> q;
        
        //初始化
        q.push_back(0);
        for(int i=1; i<k; i++) {
            while(!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }
        result.push_back(nums[q.front()]);

        //開始循環,i是每個滑動之後的起始索引
        for(int i=1; i<nums.size()-k+1; i++) {
            if(q.front() < i) {
                q.pop_front();
            }
            while(!q.empty() && nums[i+k-1] > nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i+k-1);
            result.push_back(nums[q.front()]);
        }

        return result;
    }
};
           

Python3實作：參考官方的最優解法

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) < 1 or k <= 1:
            return nums
        
        n = len(nums)
        deq = deque()
        def deque_fresh(i): #i是視窗結束位置的索引
            if deq and deq[0] == i-k:
                deq.popleft()
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()
            deq.append(i)
        
        for i in range(k):
            deque_fresh(i)
            #deq.push(i)
        result = [nums[deq[0]]]    

        for i in range(k, n, 1):
            deque_fresh(i)
            #deq.push(i)
            result.append(nums[deq[0]])
        return result