10.7 雙端佇列

239. Sliding Window Maximum

題目描述

給定一個整數陣列和一個滑動視窗大小，求在這個視窗滑動過程中的每個時刻，其包含的最大值。

輸入輸出範例

輸入是一個一維整數陣列，以及一個表示滑動視窗大小的整數；輸出是一個一維整數陣列，表示每個時刻視窗內的最大值。

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

在此範例中，滑動視窗在每個位置的最大值如下：

    Window position        Max
------------------------- -----
[1  3  -1] -3  5  3  6  7   3
 1 [3  -1  -3] 5  3  6  7   3
 1  3 [-1  -3  5] 3  6  7   5
 1  3  -1 [-3  5  3] 6  7   5
 1  3  -1  -3 [5  3  6] 7   6
 1  3  -1  -3  5 [3  6  7]  7

題解

我們可以利用雙端佇列來實現：每次滑動視窗向右移動時，將視窗左端的值從雙端佇列左端移除，並將雙端佇列右邊小於當前視窗右端值的元素剔除。這樣，雙端佇列的最左端永遠是當前視窗內的最大值。

此外，這道題也可以視為單調堆疊的一種延伸：此雙端佇列利用從左到右遞減的順序來維持大小關係。

C++

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

Python

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    dq = collections.deque()
    swm = []
    for i, num in enumerate(nums):
        if len(dq) > 0 and dq[0] == i - k:
            dq.popleft()
        while len(dq) > 0 and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            swm.append(nums[dq[0]])
    return swm