Skip to content

Latest commit

 

History

History
374 lines (283 loc) · 11.7 KB

单调队列.md

File metadata and controls

374 lines (283 loc) · 11.7 KB

特殊数据结构:单调队列

GitHub

相关推荐:

读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:

239.滑动窗口最大值

-----------

前文讲了一种特殊的数据结构「单调栈」monotonic stack,解决了一类问题「Next Greater Number」,本文写一个类似的数据结构「单调队列」。

也许这种数据结构的名字你没听过,其实没啥难的,就是一个「队列」,只是使用了一点巧妙的方法,使得队列中的元素单调递增(或递减)。这个数据结构有什么用?可以解决滑动窗口的一系列问题。

看一道 LeetCode 题目,难度 hard:

一、搭建解题框架

这道题不复杂,难点在于如何在 O(1) 时间算出每个「窗口」中的最大值,使得整个算法在线性时间完成。在之前我们探讨过类似的场景,得到一个结论:

在一堆数字中,已知最值,如果给这堆数添加一个数,那么比较一下就可以很快算出最值;但如果减少一个数,就不一定能很快得到最值了,而要遍历所有数重新找最值。

回到这道题的场景,每个窗口前进的时候,要添加一个数同时减少一个数,所以想在 O(1) 的时间得出新的最值,就需要「单调队列」这种特殊的数据结构来辅助了。

一个普通的队列一定有这两个操作:

class Queue {
    void push(int n);
    // 或 enqueue,在队尾加入元素 n
    void pop();
    // 或 dequeue,删除队头元素
}

一个「单调队列」的操作也差不多:

class MonotonicQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n,删除它
    void pop(int n);
}

当然,这几个 API 的实现方法肯定跟一般的 Queue 不一样,不过我们暂且不管,而且认为这几个操作的时间复杂度都是 O(1),先把这道「滑动窗口」问题的解答框架搭出来:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue window;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        if (i < k - 1) { //先把窗口的前 k - 1 填满
            window.push(nums[i]);
        } else { // 窗口开始向前滑动
            window.push(nums[i]);
            res.push_back(window.max());
            window.pop(nums[i - k + 1]);
            // nums[i - k + 1] 就是窗口最后的元素
        }
    }
    return res;
}

图示

这个思路很简单,能理解吧?下面我们开始重头戏,单调队列的实现。

二、实现单调队列数据结构

首先我们要认识另一种数据结构:deque,即双端队列。很简单:

class deque {
    // 在队头插入元素 n
    void push_front(int n);
    // 在队尾插入元素 n
    void push_back(int n);
    // 在队头删除元素
    void pop_front();
    // 在队尾删除元素
    void pop_back();
    // 返回队头元素
    int front();
    // 返回队尾元素
    int back();
}

而且,这些操作的复杂度都是 O(1)。这其实不是啥稀奇的数据结构,用链表作为底层结构的话,很容易实现这些功能。

「单调队列」的核心思路和「单调栈」类似。单调队列的 push 方法依然在队尾添加元素,但是要把前面比新元素小的元素都删掉:

class MonotonicQueue {
private:
    deque<int> data;
public:
    void push(int n) {
        while (!data.empty() && data.back() < n) 
            data.pop_back();
        data.push_back(n);
    }
};

你可以想象,加入数字的大小代表人的体重,把前面体重不足的都压扁了,直到遇到更大的量级才停住。

如果每个元素被加入时都这样操作,最终单调队列中的元素大小就会保持一个单调递减的顺序,因此我们的 max() API 可以可以这样写:

int max() {
    return data.front();
}

pop() API 在队头删除元素 n,也很好写:

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

之所以要判断 data.front() == n,是因为我们想删除的队头元素 n 可能已经被「压扁」了,这时候就不用删除了:

至此,单调队列设计完毕,看下完整的解题代码:

class MonotonicQueue {
private:
    deque<int> data;
public:
    void push(int n) {
        while (!data.empty() && data.back() < n) 
            data.pop_back();
        data.push_back(n);
    }
    
    int max() { return data.front(); }
    
    void pop(int n) {
        if (!data.empty() && data.front() == n)
            data.pop_front();
    }
};

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue window;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        if (i < k - 1) { //先填满窗口的前 k - 1
            window.push(nums[i]);
        } else { // 窗口向前滑动
            window.push(nums[i]);
            res.push_back(window.max());
            window.pop(nums[i - k + 1]);
        }
    }
    return res;
}

三、算法复杂度分析

读者可能疑惑,push 操作中含有 while 循环,时间复杂度不是 O(1) 呀,那么本算法的时间复杂度应该不是线性时间吧?

单独看 push 操作的复杂度确实不是 O(1),但是算法整体的复杂度依然是 O(N) 线性时间。要这样想,nums 中的每个元素最多被 push_back 和 pop_back 一次,没有任何多余操作,所以整体的复杂度还是 O(N)。

空间复杂度就很简单了,就是窗口的大小 O(k)。

四、最后总结

有的读者可能觉得「单调队列」和「优先级队列」比较像,实际上差别很大的。

单调队列在添加元素的时候靠删除元素保持队列的单调性,相当于抽取出某个函数中单调递增(或递减)的部分;而优先级队列(二叉堆)相当于自动排序,差别大了去了。

赶紧去拿下 LeetCode 第 239 道题吧~

_____________

刷算法,学套路,认准 labuladong,公众号和 在线电子书 持续更新最新文章

本小抄即将出版,微信扫码关注公众号,后台回复「小抄」限时免费获取,回复「进群」可进刷题群一起刷题,带你搞定 LeetCode

======其他语言代码======

239.滑动窗口最大值

python

由SCUHZS提供

from collections import deque

class MonotonicQueue(object):
    def __init__(self):
        # 双端队列
        self.data = deque()

    def push(self, n):
        # 实现单调队列的push方法
        while self.data and self.data[-1] < n:
            self.data.pop()
        self.data.append(n)

    def max(self):
        # 取得单调队列中的最大值
        return self.data[0]

    def pop(self, n):
        # 实现单调队列的pop方法
        if self.data and self.data[0] == n:
            self.data.popleft()


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 单调队列实现的窗口
        window = MonotonicQueue()

        # 结果
        res = []
        
        for i in range(0, len(nums)):
            
            if i < k-1:
                # 先填满窗口前k-1
                window.push(nums[i])
            else:
                # 窗口向前滑动
                window.push(nums[i])
                res.append(window.max())
                window.pop(nums[i-k+1])
        return res

java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        // 判断数组或者窗口长度为0的情况
        if (len * k == 0) {
            return new int[0];
        }

        /*
        采用两端扫描的方法
        将数组分成大小为 k 的若干个窗口, 对每个窗口分别从左往右和从右往左扫描, 记录扫描的最大值
        left[] 记录从左往右扫描的最大值
        right[] 记录从右往左扫描的最大值
         */
        int[] left = new int[len];
        int[] right = new int[len];

        for (int i = 0; i < len; i = i + k) {
            // 每个窗口中的第一个值
            left[i] = nums[i];
            // 窗口的最后边界
            int index = i + k - 1 >= len ? len - 1 : i + k - 1;
            // 每个窗口的最后一个值
            right[index] = nums[index];
            // 对该窗口从左往右扫描
            for (int j = i + 1; j <= index; j++) {
                left[j] = Math.max(left[j - 1], nums[j]);
            }
            // 对该窗口从右往左扫描
            for (int j = index - 1; j >= i; j--) {
                right[j] = Math.max(right[j + 1], nums[j]);
            }
        }

        int[] arr = new int[len - k + 1];

        // 对于第 i 个位置, 它一定是该窗口从右往左扫描数组中的最后一个值, 相对的 i + k - 1 是该窗口从左向右扫描数组中的最后一个位置
        // 对两者取最大值即可
        for (int i = 0; i < len - k + 1; i++) {
            arr[i] = Math.max(right[i], left[i + k - 1]);
        }

        return arr;
    }
}

javascript

这里用js实现的思路和上文中一样,都是自己实现一个单调队列,注意,这里的单调队列和优先级队列(大小堆)不是同一个概念。

let MonotonicQueue = function () {

    // 模拟一个deque双端队列
    this.data = [];

    // 在队尾添加元素 n
    this.push = function (n) {
        while (this.data.length !== 0 && this.data[this.data.length - 1] < n)
            this.data.pop();
        this.data.push(n);
    }

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

    // 队头元素如果是 n,删除它
    this.pop = function (n) {
        if (this.data.length !== 0 && this.data[0] === n)
            this.data.shift();
    };
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    let window = new MonotonicQueue();

    let res = []

    for (let i = 0; i < nums.length; i++) {
        if (i < k - 1) { //先把窗口的前 k - 1 填满
            window.push(nums[i]);
        } else {
            // 窗口开始向前滑动
            window.push(nums[i]);

            res.push(window.max());

            window.pop(nums[i - k + 1]);
            // nums[i - k + 1] 就是窗口最后的元素
        }
    }

    return res;

};