当前位置: 首页 > article >正文

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

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


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


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

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

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


http://www.kler.cn/news/17147.html

相关文章:

  • 【华为OD机试 2023最新 】寻找相似单词(C语言题解 100%)
  • Java中的字符串是如何处理的?
  • 【Java入门合集】第二章Java语言基础(二)
  • 【Matlab】基于改进的 Hausdorf 距离的DBSCAN船舶航迹聚类
  • 力扣(LeetCode)1172. 餐盘栈(C++)
  • 电脑中病毒了怎么修复,计算机Windows系统预防faust勒索病毒方法
  • RUST 每日一省:泛型约束——trait
  • Java面试题JVM JDK 和 JRE
  • 9:00进去,9:05就出来了,这问的也太···
  • 麻雀键值数据库开发日志
  • Linux常用的压缩、解压缩以及scp远程传输命令的使用
  • Android中Paint字体的灵活使用
  • 如何将 Elasticsearch 和时间序列数据流用于可观察性指标 - 8.7
  • 宏观经济笔记--CPI和PPI
  • 使用rt thread studio新建一个rt thread工程的详细操作说明(以stm32F411CEU6)为例
  • Python---多线程编程、基于Socket完成服务端程序开发、基于Socket完成客户端程序开发
  • SpringMVC详细介绍和@RequestMapping详细使用说明
  • 预制菜,巨头们的新赛场
  • python3 强制使用任意父级相对导入,越过python相对导入限制,拒绝 ImportError
  • 操作系统——设备管理
  • kafka的安装与使用
  • 关于低代码开发平台的一些想法
  • 【Frame.h】
  • 手写堆priority_queue优先队列
  • 题目:16版.学生-成绩关联实体
  • Centos7快速安装Kibana并连接ES使用
  • 结合SSE实现实时位置展示与轨迹展示
  • 区块链系统探索之路:基于椭圆曲线的私钥与公钥生成
  • FPGA/Verilog HDL/AC620零基础入门学习——8*8同步FIFO实验
  • spring-模型数据和视图---视图解析器的说明以及大量代码演示