您现在的位置是:首页 >其他 >数据结构与算法(十一) 单调栈与单调队列网站首页其他

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

半虹 2023-07-24 12:00:02
简介数据结构与算法(十一) 单调栈与单调队列

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


1  单调栈

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

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

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


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

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


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

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

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

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

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

当前元素当前元素入栈前
栈状态
更小元素出栈后
栈状态
下一个更大元素当前元素入栈后
栈状态
4[][]/[4]
5[4][]/[5]
1[5][5]5[5, 1]
3[5, 1][5]5[5, 3]
2[5, 3][5, 3]3[5, 3, 2]

对应代码如下:

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

给定数组 nums1nums2 ,求 nums1 中每个元素的下一个更大元素

nums1 中元素 x 的下一个更大元素是指 xnums2 中对应位置右侧第一个比 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;
    }
};
  1. 下一个更大元素 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;
    }
};
  1. 每日温度 | 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:窗口左端右移一步,窗口右端右移一步

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

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

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

步骤当前元素初始队列状态出队元素出队后队列状态进队元素进队后队列状态最大
14[]/[]4[4]/
25[4]/[4]5[5]/
3 (k)3[5]/[5]3[5, 3]5
42[5, 3]4[5, 3]2[5, 3, 2]5
51[5, 3, 2]5[3, 2]1[3, 2, 1]3
64[3, 2, 1]3[2, 1]4[4]4
73[4]2[4]3[4, 3]4
8 (n)2[4, 3]1[4, 3]2[4, 3, 2]4

对应代码如下:

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


好啦,本文到此结束,感谢您的阅读!

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

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

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。