单调队列结构解决滑动窗口问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：单调队列结构解决滑动窗口问题

评论礼仪 见这里，违者直接拉黑。

[kingfive]

這邊提醒一下，如果在push element 進入 Monotonic Queue 時，把條件設做 q.peekLast() <= ele 在這個test case - [7,5,7,1,6,0] 3 會出錯。
原因是當我們要pop element 時會移除第一個element 也就是 7，這就把我們 Monotonic Queue的唯一的7 (先前的7被擠掉了) 給pop掉了。
所以只能使用 q.peekLast() < ele 來做判斷

[zhangshuiyong]

插入节点可以使用新结构体 Node{val int ,index int}，来排除val相同，但是应该删除的index不匹配问题

[JiaRuiShao]

public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length, left;
        if (n == 0) {
            return nums;
        }
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            left = i - k + 1;

            while (!dq.isEmpty() && nums[i] > dq.peekLast()) {
                dq.pollLast();
            }
            dq.offerLast(nums[i]);

            if (left >= 0) {
                res[left] = dq.peekFirst();
                if (!dq.isEmpty() && dq.peekFirst() == nums[left]) {
                    dq.pollFirst();
                }
            }
        }
        return res;
    }

[acse-yw3821]

CPP version

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> res;
        for(int i=0; i<k; i++)
            que.push(nums[i]);
        res.push_back(que.front());

        for(int i=k; i<nums.size(); i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }

private:
    class MyQueue{
    public:
        deque<int> que;

        void pop(int val){
            if(!que.empty() && que.front()==val)
                que.pop_front();
        }

        void push(int val){
            while(!que.empty() && val>que.back())
                que.pop_back();
            que.push_back(val);
        }

        int front(){
            return que.front();
        }
    };
};

[David-qiuwenhui]

javascript version:

var maxSlidingWindow = function(nums, k) {
    let window = new monotonicQueue();
    let res = [];
    for (let i=0; i<nums.length; i++) {
        // 先把窗口的前k-1个元素填满
        if (i < k - 1) {
            window.push(nums[i]);
        } else {
            // 窗口开始向前滑动
            // 移入新元素
            window.push(nums[i]);
            // 将当前窗口中的最大元素计入结果
            res.push(window.max());
            // 移出最后的元素
            window.pop(nums[i - k + 1]);
        }
    }
    return res;
};

var monotonicQueue = function () {
    let queue = [];
    // 在队尾添加元素n
    this.push = function (n) {
        while (queue.length && n > queue[queue.length - 1]) {
            queue.pop();
        }
        queue.push(n);
    };

    // 返回当前队列中的最大值
    this.max = function () {
        // 队头元素是最最大值
        return queue[0];
    };

    // 队头元素如果是n，删除它
    this.pop = function (n) {
        if (n == queue[0]) {
            queue.shift();
        }
    };
};

[CyrusHelios]

shift()方法的时间复杂度是O(n)

[hwhaocool]

1楼说的有道理， push 的时候的确必须使用 <， 而不能 <=，否则在 pop 的时候，最大值会被删掉

[saw008]

请教各位一个问题哎，我使用python手动定义了双链表，虽然可以通过所有用例，但为什么最后运行时间和使用内存都很多呢？按说应该很快的呀。代码如下

class MonotonicQueue:
    def __init__(self):
        self.mq = DLList()
    def push_in(self, n):
        while self.mq.get_size() and self.mq.peek_last() < n:
            self.mq.pop_last()
        self.mq.insert(n)
    def peek(self):
        return self.mq.peek_first()
    def pop_out(self, n):
        if self.mq.peek_first() == n:
            self.mq.pop_first()

# Doubly Linked List Node class
class DLLNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class DLList:
    def __init__(self):
        self.head = DLLNode(-1)
        self.tail = DLLNode(-1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    def insert(self, n):
        # insert to the last position
        new_node = DLLNode(n)
        self.tail.prev.next = new_node
        new_node.prev = self.tail.prev
        new_node.next = self.tail
        self.tail.prev = new_node
        self.size += 1
    def pop_last(self):
        self.pop_node(self.tail.prev)
    def pop_first(self):
        self.pop_node(self.head.next)
    def pop_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.next = None
        node.prev = None
        self.size -= 1
    def peek_last(self):
        return self.tail.prev.val
    def peek_first(self):
        return self.head.next.val
    def get_size(self):
        return self.size
    
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        mq = MonotonicQueue()
        ans = []
        for i in range(len(nums)):
            if i < k-1:
                mq.push_in(nums[i])
            else:
                mq.push_in(nums[i])
                ans.append(mq.peek())
                mq.pop_out(nums[i+1-k])
        return ans

[ngokchaoho]

感覺自定義的class都有一堆沒有用到的attributes佔用了空間。訪問這些attribute，也要進行look up。https://python-history.blogspot.com/2010/06/inside-story-on-new-style-classes.html
用上__slot__會有改善。

[lpdswing]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        window = MonotonicQueue()
        res = []
        n = len(nums)
        for i in range(n):
            if i < k-1:
                window.push(nums[i])
            else:
                window.push(nums[i])
                res.append(window.max())
                window.pop(nums[i-k+1])
        return res


class MonotonicQueue:

    def __init__(self):
        self.q = deque()

    def push(self, n):
        while self.q and self.q[-1] < n:
            self.q.pop()
        self.q.append(n)

    def max(self):
        return self.q[0]

    def pop(self, n):
        if n == self.q[0]:
            self.q.popleft()

[TinyOrange98]

单调队列的思路很棒，但是不熟悉的话有点不太好想，关于这道题，题意很清晰，就是如何动态地维护集合并高效地返回最大值。

动态集合底层常见的就是哈希表和 rb tree。维护最大值最常见的就是 heap。

我分别从 rb tree 和 heap 的角度给出几个比较直接但是讨论不多的解决方案（我大概看了一下相关题解，大多数都是讲单调队列，以及堆的延迟删除（我的实现方案和大多数题解略有不同））：

RB-TREE 方案：

我们可以动态地维护一个容量为 K 的平衡树，那么最大值就是平衡树的最右节点，同时当窗口向右滑动时，删除左边界元素，并添加右边界元素即可。

C++ STL 已经实现了 RB-TREE，我的代码实现中采用的是 multiset（因为窗口中的元素是有可能重复的），代码如下（LeetCode 执行通过）：

这种方案实现起来是这几种方案中最简单快速的。

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        typedef pair<multiset<int>::iterator, multiset<int>::iterator> srange;
        multiset<int> s;
        if (nums.size() <= k)
            return {*max_element(nums.begin(), nums.end())};
        for (int i = 0; i < k; i++)
            s.insert(nums[i]);

        vector<int> ans;
        int j = k, size = nums.size();
        while (j < size)
        {
            ans.push_back(*(--s.end()));
            s.insert(nums[j]);
            srange range = s.equal_range(nums[j - k]);
            s.erase(range.first);
            j++;
        }
        ans.push_back(*(--s.end()));
        return ans;
    }
};

HEAP && HASH-TABLE && 延迟删除

我们可以维护一个大根堆来快速寻找最大值，但是在窗口滑动过程中需要删除左边界的元素，对于堆来讲，删除堆顶元素很容易，但是删除队中的任意元素不太容易（因为标准的heap接口并不支持随机删除heap中元素的功能，我在第三种解决方案中手动实现了这一API），所以可以考虑采用变相删除。

大多数题解都是通过比较索引大小关系来实现的，我的实现方案是定义一个node结构体，node包含数据本身以及一个名称为del的bool变量，del默认为false表示该元素没有被删除。如果标记为true表示已经被删除，那么在弹出元素的时候就会忽略del为true的元素。

为了能够快速获取到heap中元素的地址，还需要一个hash-table存储数据到node地址的映射关系，采用unordered_multimap实现，原因还是因为窗口中数据可能会重复。

代码如下（LeetCode 执行通过）:

这种方案略微复杂。

struct node
{
    int val;
    bool del;
    node(int __val) : val(__val), del(false) {}
};

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        if (nums.size() <= k)
            return {*max_element(nums.begin(), nums.end())};

        typedef pair<unordered_multimap<int, node *>::iterator, unordered_multimap<int, node *>::iterator> prange;
        auto comp = [](node *a, node *b)
        {
            return a->val < b->val;
        };
        priority_queue<node *, vector<node *>, decltype(comp)> q(comp);
        unordered_multimap<int, node *> val2addr;

        vector<int> ans;
        for (int i = 0; i < k; i++)
        {
            node *addr = new node(nums[i]);
            q.push(addr);
            val2addr.insert({nums[i], addr});
        }

        int size = nums.size(), j = k;
        while (j < size)
        {
            while (q.top()->del == true)
                q.pop();

            ans.push_back(q.top()->val);
            node *addr = new node(nums[j]);
            q.push(addr);
            val2addr.insert({nums[j], addr});

            prange range = val2addr.equal_range(nums[j - k]);
            range.first->second->del = true;
            val2addr.erase(range.first);
            j++;
        }
        while (q.top()->del == true)
            q.pop();

        ans.push_back(q.top()->val);
        return ans;
    }
};

HEAP && HASH-TABLE && 立即删除

第一种以及第二种解决方案已经足够好了，这种解决方案只是作为一种补充，要想实现立即删除heap中任意元素的功能，我们需要做两件事情。

第一件事情就是存储数据到数据在heap中索引的映射，这部分采用unordered_multimap实现。

第二件事情是实现一个随机删除的接口，我们最常见的是删除堆顶元素，很少见随机删除堆内部元素，但是这个实现方案很简单。

堆是一棵完全二叉树，假设从1开始编号，一直到n，那么对于编号为i的元素，我们只需要将其与编号为n的元素互换并且删除堆尾部的元素，然后重新对堆进行调整即可。

交换元素后，编号为i的元素可能破坏堆的性质，调整方案如下：连续调用上浮和下沉这两个接口即可。编号为i的元素与其父亲节点（如果有的话）以及子女节点（如果有的话）的关系有且只有三种关系：

1、堆的性质继续保持，无需做任何调整。
2、需要下沉。
3、需要上浮。

绝对不会出现别的情况，所以连续调用上浮与下沉就可以覆盖所有情况，实际上要么这两个操作一个都不会执行，要么只执行一个，绝不会既上浮又下沉。（ps：随机删除heap中的元素是《算法导论》中的一道练习题）

代码如下（LeetCode执行通过）：

这种方案最复杂，因为需要自己实现一个堆，只是代码量略大而已，并不难。

struct heap
{
    typedef pair<unordered_multimap<int, int>::iterator, unordered_multimap<int, int>::iterator> prange;

    vector<int> __heap;
    unordered_multimap<int, int> elm2ind;

    void __swap(int __x, int __y)
    {
        prange x_range = elm2ind.equal_range(__heap[__x]);
        prange y_range = elm2ind.equal_range(__heap[__y]);
        for (auto it = x_range.first; it != x_range.second; it++)
            if (it->second == __x)
            {
                it->second = __y;
                break;
            }

        for (auto it = y_range.first; it != y_range.second; it++)
            if (it->second == __y)
            {
                it->second = __x;
                break;
            }

        swap(__heap[__x], __heap[__y]);
    }

    void up(int pos)
    {
        int parent = (pos - 1) >> 1;
        while (parent >= 0 && __heap[parent] < __heap[pos])
        {
            __swap(parent, pos);
            pos = parent;
            parent = (pos - 1) >> 1;
        }
    }

    void down(int pos)
    {
        int left = (pos << 1) + 1, right = (pos << 1) + 2;
        int size = __heap.size();
        while (left < size)
        {
            int y = pos;
            if (__heap[left] > __heap[y])
                y = left;
            if (right < size && __heap[right] > __heap[y])
                y = right;
            if (y != pos)
            {
                __swap(pos, y);
                pos = y;
                left = (pos << 1) + 1, right = (pos << 1) + 2;
            }
            else
                break;
        }
    }

    void random_delete(int data)
    {
        prange range = elm2ind.equal_range(data);
        int pos = range.first->second;
        int size = __heap.size();

        __swap(pos, size - 1);
        __heap.pop_back();
        elm2ind.erase(range.first);

        //关键调整操作
        up(pos);
        down(pos);
    }

    int &top()
    {
        return __heap[0];
    }

    void push(int data)
    {
        __heap.push_back(data);
        elm2ind.insert({data, __heap.size() - 1});
        up(__heap.size() - 1);
    }
};

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        heap h;
        if (nums.size() <= k)
            return {*max_element(nums.begin(), nums.end())};

        for (int i = 0; i < k; i++)
            h.push(nums[i]);

        vector<int> ans;
        int j = k;
        while (j < nums.size())
        {
            ans.push_back(h.top());
            h.random_delete(nums[j - k]);
            h.push(nums[j]);
            j++;
        }
        ans.push_back(h.top());
        return ans;
    }
};

时间复杂度

三种方案中，第一种方案执行568ms,第二种执行692ms,第三种1132ms。执行时间虽然有差别，但只是常数差别而已，不存在阶的差异，基本操作要么是常量要么就是对数级别。不严格的分析，理论上来讲，第一种时间复杂度是 O(N LOG(K)),第二种时间复杂度是O(N LOG(N))(因为最坏情况下堆中的元素数量是N所以真数大一些，但是没什么大的影响，因为LOG在实际表现中近乎常量阶)，第三种时间复杂度是O(N LOG(K))。

[labuladong]

👍👍👍

[yonggui-yan]

打卡，点赞

[LCAIZJ]

python如何使用list作为linkedlist的实现会超时

[wild-chigga]

用collections.deque

[wild-chigga]

py3已ac，请各位指正

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        n = len(nums)
        stack = collections.deque()
        w = collections.deque()

        for i in range(k):
            w.append(nums[i])

            if not stack or stack[-1] >= nums[i]: 
                stack.append(nums[i])
                continue
            
            while stack and stack[-1] < nums[i]:
                stack.pop()
            stack.append(nums[i])

        cur_max = stack[0]
        res.append(cur_max)
        
        idx = k-1
        while idx < n-1:
            if w.popleft() == stack[0]:
                stack.popleft()

            idx += 1
            w.append(nums[idx])
            while stack and stack[-1] < nums[idx]:
                stack.pop()
            stack.append(nums[idx])

            res.append(stack[0])

        return res

[weixueman]

扩展延伸：额外用一个LinkedList保存当前单调队列中的实际元素，这样poll()方法就不用传递元素了，单调队列的size()方法则调用这个队列的size()方法；获取最小值的min()方法与max()方法类似，申请一个LindkedList实现从小到大存储元素

[bruceeewong]

接 @weixueman 的思路，实现了一下拓展，放到sliding window题里通过了。思路就是多维护一个存全部元素的queue以及minq

/* 单调队列的通用实现，可以高效维护最大值和最小值 */
class MonotonicQueue<E extends Comparable<E>> {
    LinkedList<E> queue;
    LinkedList<E> maxq;
    LinkedList<E> minq;

    public MonotonicQueue() {
        queue = new LinkedList<>();
        maxq = new LinkedList<>();
        minq = new LinkedList<>();
    }

    // 标准队列 API，向队尾加入元素
    public void push(E elem) {
        queue.addLast(elem);

        while (!maxq.isEmpty() && maxq.getLast().compareTo(elem) < 0) {
            maxq.pollLast();
        }
        maxq.addLast(elem);

        while (!minq.isEmpty() && minq.getLast().compareTo(elem) > 0) {
            minq.pollLast();
        }
        minq.addLast(elem);
    }

    // 标准队列 API，从队头弹出元素，符合先进先出的顺序
    public E pop() {
        if (size() == 0) return null;

        E first = queue.pollFirst();
        if (maxq.getFirst().equals(first)) {
            maxq.pollFirst();
        }
        if (minq.getFirst().equals(first)) {
            minq.pollFirst();
        }
        return first;
    }

    // 标准队列 API，返回队列中的元素个数
    public int size() {
        return queue.size();
    }

    // 单调队列特有 API，O(1) 时间计算队列中元素的最大值
    public E max() {
        return maxq.getFirst();
    }

    // 单调队列特有 API，O(1) 时间计算队列中元素的最小值
    public E min() {
        return minq.getFirst();
    }
}

[fancygeek]

请教：
为什么是先移入元素，取最大值，再移除元素？
不应该是移出元素，移入元素，再取最大值吗？

[kymmo]

按照我的理解，按照labuladong的方式设置 i 指针是 window 的最右端的话，实际上 i 是指向window的最右边下一个位置的。所以如果是移出移入再判断，最后一个 window 还没有处理就退出循环了。
如果你想要 移出移入再判断 ，需要对上述这些情况做兼容。或者用其他方式设置 i 指针。