fucking-algorithm

fucking-algorithm copied to clipboard

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

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

這邊提醒一下，如果在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 來做判斷

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

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;
    }

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();
        }
    };
};

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();
        }
    };
};

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

请教各位一个问题哎，我使用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

没有人解答拓展延申吗？

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

动态集合底层常见的就是哈希表和 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))。