数据结构与算法(十一) 单调栈与单调队列

大家好，我是半虹，这篇文章讲单调栈和单调队列

1  单调栈

栈是一种很常见的数据结构，具有后进先出的特点

而单调栈则是一种特殊的栈，在进栈出栈时，通过某些操作使栈内元素保持单调性

在这里，栈内元素的单调性是指元素单调递增或者单调递减

单调栈的应用场景并不多，最典型的莫过于下一个更大元素，更小元素同理可求

简单来说就是对于数组中的每个元素，找到下一个比自己大的元素及其所在位置

举个例子，给定数组 [2, 3, 1, 5, 4]，位置从 0 开始算

• 对于元素 2，下一个更大元素是 3，其所在位置是 1
• 对于元素 3，下一个更大元素是 5，其所在位置是 3
• 对于元素 1，下一个更大元素是 5，其所在位置是 3
• 对于元素 5，下一个更大元素不存在 /
• 对于元素 4，下一个更大元素不存在 /

使用单调栈怎么解决呢？我们只需要去反向遍历一次数组，并将元素依次进栈

同时在每个元素进栈前，先将栈内小于等于它的元素出栈，此时栈顶元素即为下一个更大元素

在整个进栈出栈过程中，栈内元素始终保持单调递增状态，所以被称为单调栈

对应代码如下：

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return {};
    }
    vector<int> r(n);
    stack <int> s;
    // 反向遍历
    for (int i = n - 1; i >= 0; i--) {
        // 更小元素出栈
        while (!s.empty() && s.top() <= nums[i]) s.pop();
        // 下一更大元素
        r[i] = !s.empty() ?  s.top() : -1;
        // 当前元素入栈
        s.push(nums[i]);
    }
    return r;
}

相关例题如下：

1. 下一个更大元素 I  | leetcode496

给定数组 nums1 和 nums2 ，求 nums1 中每个元素的下一个更大元素

nums1 中元素 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧第一个比 x 大的元素

先用单调栈求 nums2 中每个元素的下一个更大元素

再用哈希表存 nums2 中每个元素与下一个更大元素的对应关系

最后遍历一次 nums1 在哈希表中找下一个更大元素

class Solution {
public:
    vector<int> nextGreaterElement( vector<int>& nums1, vector<int>& nums2 ) {

        vector<int> nextG = myNextGreaterElement(nums2);

        unordered_map<int, int> map;
        for (int i = 0; i < nums2.size(); i++) {
            map[nums2[i]] = nextG[i];
        }

        vector<int> ans(nums1.size());
        for (int i = 0; i < nums1.size(); i++) {
            ans[i] = map[nums1[i]];
        }
        return ans;
    }

    // 模板
    vector<int> myNextGreaterElement(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return {};
        }
        vector<int> r(n);
        stack <int> s;
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && s.top() <= nums[i]) s.pop();
            r[i] = !s.empty() ?  s.top() : -1;
            s.push(nums[i]);
        }
        return r;
    }
};

2. 下一个更大元素 II | leetcode503

给定数组 nums ，求数组中每个元素的下一个更大元素，但该数组是循环数组

处理循环数组最简单的方法，就是复制一份数组拼到后面，然后其他的操作和之前一样

但是在实现时，我们无需真正复制一份数组，而是可以通过修改遍历方式模拟这个过程

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return {};
        }
        vector<int> r(n);
        stack <int> s;
        // 起始从 n - 1 变成 n * 2 - 1
        for (int i = n * 2 - 1; i >= 0; i--) {
            // 取值从 i 变成 i % n
            while (!s.empty() && s.top() <= nums[i % n]) s.pop();
            r[i % n] = !s.empty() ?  s.top() : -1;
            s.push(nums[i % n]);
        }
        return r;
    }
};

3. 每日温度 | leetcode739

给定数组 nums ，求数组中每个元素的下一个更大元素与当前元素之间的距离

还是用单调栈，但栈内保存的是索引而非值

然后在出栈时，计算当前元素与下一个更大元素之间的距离

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return {};
        }
        vector<int> r(n);
        stack <int> s;
        for (int i = n - 1; i >= 0; i--) {
            // 栈保存索引
            // 入栈时计算下一个更大元素和当前元素相差的距离
            while (!s.empty() && nums[s.top()] <= nums[i]) s.pop();
            r[i] = !s.empty() ?  s.top() - i : 0;
            s.push(i);
        }
        return r;
    }
};

2  单调队列

队列也是很常见的数据结构，具有先进先出的特点

单调队列是一种特殊的队列，在进队出队时，通过某些操作使队内元素保持单调性

在这里，队内元素的单调性是指元素单调递增或者单调递减

单调队列的应用场景很少，其通常会配合滑动窗口一起使用来求解滑动窗口最大值

一道典型的例题如下所示：leetcode239

给定整数数组 nums，给定窗口大小 k，窗口从数组最左侧滑动到数组最右侧，求窗口每次移动最大值

输入：nums = [4, 5, 3, 2, 1, 4, 3, 2]，k = 3；输出：[3, 3, 5, 5, 6, 7]
解释：

       滑动窗口的位置     当前窗口最大值
    [4 5 3] 2 1 4 3 2        5
    4 [5 3 2] 1 4 3 2        5
    4 5 [3 2 1] 4 3 2        3
    4 5 3 [2 1 4] 3 2        4
    4 5 3 2 [1 4 3] 2        4
    4 5 3 2 1 [4 3 2]        4

解题的关键是当窗口移动时，如何维护窗口的最大值，这里就要用到单调队列，具体步骤如下：

1. 初始阶段，步骤1 ~ k：窗口左端保持不变，窗口右端右移一步
2. 更新阶段，步骤k ~ n：窗口左端右移一步，窗口右端右移一步

窗口左端右移，意味着旧窗口左端元素出队，如果该元素已不在队列，那么无事发生

窗口右端右移，意味着新窗口右端元素进队，注意该元素在进队之前，要先将队列中小于等于它的元素出队

在进队出队时，队内元素始终保持单调递增，所以这被称为单调队列，该队列具体用双端队列实现

对应代码如下：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == 0) {
            return {};
        }
        vector<int> r;
        deque <int> q;
        // 初始阶段
        for (int i = 0; i < k; i++) {
            // 新窗口右端元素进队
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
        }
        r.push_back(nums[q.front()]); // 保存结果
        // 更新阶段
        for (int i = k; i < n; i++) {
            // 旧窗口左端元素出队
            while (!q.empty() && q.front() <= i - k) {
                q.pop_front();
            }
            // 新窗口右端元素进队
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
            r.push_back(nums[q.front()]); // 保存结果
        }
        // 返回结果
        return r;
    }
};

好啦，本文到此结束，感谢您的阅读！

如果你觉得这篇文章有需要修改完善的地方，欢迎在评论区留下你宝贵的意见或者建议

如果你觉得这篇文章还不错的话，欢迎点赞、收藏、关注，你的支持是对我最大的鼓励 (/ω＼)