算法数据结构--单调栈

2024-05-04 03:28
文章标签 算法 数据结构 单调

本文主要是介绍算法数据结构--单调栈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 介绍
      • 单调递增栈
      • 单调递减栈
      • 图示
      • 应用场景
    • 步骤
    • 模板
    • Deque用法
    • 例题
      • [739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)
      • [496. 下一个更大元素 I](https://leetcode.cn/problems/next-greater-element-i/)
    • 总结

介绍

单调栈是一种特殊的栈数据结构,其特点在于栈内的元素保持单调性。单调栈通常分为单调递增栈和单调递减栈两种类型。

单调递增栈

​ 单调递增栈中的元素从栈底到栈顶依次递增。当我们向单调递增栈中压入一个元素时,如果该元素比栈顶元素大,就直接入栈;如果该元素比栈顶元素小,则不断将栈顶元素出栈,直到栈为空或者栈顶元素小于等于当前元素,然后再将当前元素入栈。单调递增栈主要用于解决一些需要找到右边第一个较大元素的问题。

单调递减栈

​ 单调递减栈中的元素从栈底到栈顶依次递减。当我们向单调递减栈中压入一个元素时,如果该元素比栈顶元素小,就直接入栈;如果该元素比栈顶元素大,则不断将栈顶元素出栈,直到栈为空或者栈顶元素大于等于当前元素,然后再将当前元素入栈。单调递减栈主要用于解决一些需要找到右边第一个较小元素的问题。

图示

在这里插入图片描述

应用场景

单调栈在解决一些数组或序列相关问题时非常有效。

例如:

  • 寻找数组中下一个较大或较小元素;
  • 计算滑动窗口的最大值或最小值;
  • 解决一些与序列相关的动态规划问题;
  • 解决一些需要找到数组中局部极值或单调性的问题等。

步骤

单调栈的步骤一般分为:

  1. 定义一个栈

    Deque<Integer> deque=new ArrayDeque<Integer>();
    
  2. 确定栈里存储的数据是什么

    一般情况下单调栈里面存放的都是目标数组的下标,这样做的好处就是,我们不仅知道遍历过的元素下标,而且也可以通过下标找到对应数组里面的元素。

  3. 确定使用单调递增栈还是单调递减栈

    如果求一个元素右边第一个更大元素时,单调栈就是递增的,如果求一个元素右边第一个更小元素,单调栈就是递减的。

  4. 遍历目标数组,比较当前遍历的元素与栈顶元素,并进行处理
    这里在遍历目标数组的时候,需要比较当前遍历元素和栈顶元素的大小。
    这个时候就有如下三种情况:

    • 当前遍历的元素小于栈顶元素的情况
    • 当前遍历的元素等于栈顶元素的情况
    • 当前遍历的元素大于栈顶元素的情况

    一般情况下单调递增栈在当前遍历的元素大于栈顶元素的情况下进行主要的逻辑处理,其他情况下直接把当前元素做入栈操作;而单调递减栈在当前遍历的元素小于栈顶元素的情况下进行主要的逻辑处理,其他情况下直接把当前元素做入栈操作。

    注意:在对栈进行操作的时候,要尽量减少对栈的操作次数。比如,如果在获取栈顶元素后,还要进行弹出操作且再获取栈顶元素后不需要在将该元素保留栈顶。则此时,可以直接使用pop()方法,代替使用peek()方法后再使用pop()方法。

  5. 返回结果

模板

import java.util.*;public class MonotonicStackSolver {// 单调递增栈public void solveIncreasing(int[] nums) {Deque<Integer> stack = new ArrayDeque<>();// 遍历数组for (int i = 0; i < nums.length; i++) {// 维护单调性while (!stack.isEmpty() && nums[i] < stack.peek()) {stack.pop();// 在这里可以执行相关操作}// 入栈stack.push(nums[i]);}}// 单调递减栈public void solveDecreasing(int[] nums) {Deque<Integer> stack = new ArrayDeque<>();// 遍历数组for (int i = 0; i < nums.length; i++) {// 维护单调性while (!stack.isEmpty() && nums[i] > stack.peek()) {stack.pop();// 在这里可以执行相关操作}// 入栈stack.push(nums[i]);}}public static void main(String[] args) {MonotonicStackSolver solver = new MonotonicStackSolver();// 示例用法int[] nums = {2, 5, 9, 3, 1, 12, 6, 8};solver.solveIncreasing(nums); // 使用单调递增栈解决问题// 或者solver.solveDecreasing(nums); // 使用单调递减栈解决问题}
}

Deque用法

我们在用Java写单调栈题目的时候一般需要用到以下这几个方法:

  • deque.isEmpty():如果deque不包含任何元素,则返回true,否则返回false。因为要栈顶元素在满足要求的时候要弹出,所以需要进行空栈判断。有些场景,可能栈一定不会空的时候,就不需要该方法进行空栈判断。
  • deque.push(e):将元素e入栈。
  • deque.pop():将栈顶元素弹出,并返回当前弹出的栈顶元素。
  • deque.peek():获取栈顶元素,不弹出。

例题

下面我们用两个简单的例题来加深我们对单调栈的理解:

739. 每日温度

在这里插入图片描述

本题意思就是让我们去找每一个元素下一个比他更大的元素出现在后面的哪里,如果有则记录下标之差,如果没有则设置为0,最后返回答案数组。

我们看下代码:

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] ans = new int[temperatures.length];//定义答案数组Deque<Integer> stack = new ArrayDeque<Integer>();//定义一个栈for (int i = 0; i < temperatures.length; i++) {while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {//如果栈不为空且遍历的元素大于栈顶元素,那么就要出栈,并且此时也证明栈顶元素找到了下一个比它更大的元素的位置,记录下标之差就可以了int m = stack.pop();//弹出栈顶元素(下标)ans[m] = i - m;//用此时遍历的元素下标减去栈顶元素下标就是栈顶元素下标下一个比他温度更高的天数}stack.push(i);//其他情况(栈为空或者遍历元素小于等于栈顶元素)都入栈}return ans;//返回答案}
}

我们往栈内存储的元素是下标而不是元素数值,这样我们就可以很容易地求出下标之差。

用Deque比自己创建一个数组来表示栈更方便一点

496. 下一个更大元素 I

在这里插入图片描述

本题就是让我们去找在nums1中出现过的数字在nums2中去找比它大的第一个数字是多少,答案要存储在nums1中的对应下标位置。

本题我们很容易就可以联想到要使用哈希表去存储nums1中出现过的数字,当循环nums2数组的时候就可以直接判断存在不存在了。

下面我们直接来看代码:

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] hash = new int[10001];for (int i = 0; i < nums1.length; i++) {hash[nums1[i]] = i + 1;//这里可以将哈希表对应下标位置的数值直接设置成i+1,这样在之后记录答案的时候直接在答案数组hash[]-1的位置记录就可以了}Deque<Integer> stack = new ArrayDeque<Integer>();int[] ans = new int[nums1.length];int ansTop = 0;for (int i = 0; i < nums1.length; i++)ans[i] = -1;for (int i = 0; i < nums2.length; i++) {while(!stack.isEmpty()&&nums2[i]>nums2[stack.peek()]){int m = stack.pop();ans[hash[nums2[m]]-1] = nums2[i];}if(hash[nums2[i]]!=0)//遍历的数字在nums1中出现过才能入栈stack.push(i);}while(!stack.isEmpty()){int m = stack.pop();ans[hash[nums2[m]]-1] = -1;//栈内剩余的部分就是后面没有比他大的数字,直接设置成-1就可以了}return ans;}
}

总结

总的来说,单调栈是一种高效、简洁且灵活的数据结构。

单调栈的空间复杂度通常很低,因为它只需要存储输入序列中的一部分元素,而不需要额外的空间。

通常情况下,单调栈的时间复杂度为 O(n),其中 n 为输入序列的长度。这是因为在大多数情况下,每个元素最多进栈一次、出栈一次,所以整个过程的时间复杂度是线性的。

所以单调栈在解决数组或序列相关问题时具有很好的效果。

已经到底啦!!

这篇关于算法数据结构--单调栈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/958247

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为