Leetcode 239. Sliding Window Maximum

窗口從左向右滑動，計算每個窗口中子數列的最大值

Python

方法一 : 迴圈

每k個數成一組，透過滑動視窗(往右一位)，並在每個數組裡面求最大值，最後全部append到新的list

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums)==0:
            return []
        if k==0:
            return None
        a = []
        for i in range(len(nums)-k+1):
            a.append(max(nums[i:i+k]))
        return a

方法二 : deque 雙端佇列

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        opt = []
        q = collections.deque()
        for i in xrange(len(nums)):
            n = nums[i]
            
            #移動視窗
            if q and q[0]<=i-k: q.popleft()

            #如果隊列中的元素不大於傳入的元素，則彈出右側
            #通過這樣做，我們可以始終將當前窗口中的最大值保持在最左側
            while q and nums[q[-1]]<=n: q.pop()
            q.append(i)

            #在第一個第 k 個元素之後將最大值添加到輸出數組
            if 1+i>=k: opt.append(nums[q[0]])
        return opt

C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq; // 雙端隊列用於存儲窗口中可能成為最大值的元素的下標
        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() == i - k) { // 如果雙端隊列中存儲的元素已經超出窗口大小，將其彈出
                dq.pop_front();
            }
            while (!dq.empty() && nums[i] > nums[dq.back()]) { // 如果當前元素比隊尾元素大，將隊尾元素彈出
                dq.pop_back();
            }
            dq.push_back(i); // 將當前元素的下標加入雙端隊列中
            if (i >= k - 1) { // 當窗口大小為k時，雙端隊列的隊首元素即為當前窗口中的最大值
                res.push_back(nums[dq.front()]);
            }
        }
        return res;
    }
};

Python

C++

相關