前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >谁还不会单调栈

谁还不会单调栈

原创
作者头像
marsxingzhi
发布2023-07-13 11:27:19
2100
发布2023-07-13 11:27:19
举报

什么是单调栈

单调栈是满足单调性的栈,即在栈的基础上,维持栈内元素的单调性。典型题目如:有找某侧最近一个比其大(小)的值

一般来说:1. 找某侧最近一个比其大的值,使用单调栈维持栈内元素递减;2. 找某侧最近一个比其小的值,使用单调栈维持栈内元素递增。(建议不要死记硬背,做题目时,随机挑选单调增或单调减进行模拟,不是挑选的这个,就是另外一个)

代码格式如下:

代码语言:go
复制
var stack []int
var tt int 

// 遍历数组
for i := 0; i < n; i++ {
  // 如果栈不为空,且不符合单调减了,需要将元素从栈中弹出
  for tt > 0 && nums[i] > nums[stack[tt]] {
    // 具体的逻辑
  }
  // 具体逻辑
}

示例

元素A左侧第一个比它大的元素

元素A左侧第一个比它大的元素C,首先肯定是单调减,也是有两种写法的,即顺序和逆序。(我建议一般使用顺序)

代码语言:go
复制
for i := 0; i < n; i++ {
    
    for tt > 0 && nums[i] >= nums[stack[tt]] {
        tt--
    }
    
    val := -1
    if tt > 0 {
        val = nums[stack[tt]]
    }
    // 元素A左侧第一个比它大的元素
    ans[i] = val
    
    
    tt++
    stack[tt] = i
}

元素A左侧第一个比它小的元素

首先还是明确一下,这个是单调增,应该还是有两种写法,顺序和逆序。

代码语言:go
复制
for i := 0; i < n; i++ {
    
    for tt > 0 && nums[i] <= nums[stack[tt]] {
        tt--
    }
    val := -1
    if tt > 0 {
        // 存在元素A左侧第一个比它小的元素C
        val = nums[stack[tt]]
    }
    ans[i] = val
    
    tt++
    stack[tt] = i
}

元素B右侧第一个比它大的元素

元素B右侧第一个比它大的元素C,首先明确一下,这个是单调减,有两种做法,分别对应顺序和逆序。

仔细对比一下两者的区别,两者相对的参考是不一样的,一个是固定元素C,一个是固定元素B,由于固定的元素不同,因此逻辑写在不同的地方,一个是在回退栈的过程中处理,一个是在回退栈之后处理。

方式一:顺序写法

代码语言:go
复制
for i := 0; i < n; i++ {
    
    for tt > 0 && nums[i] > nums[stack[tt]] {
        // 对于下标为stack[tt]的元素,其右侧第一个比它大的元素为nums[i]
        ans[stack[tt]] = nums[i]
        tt--
    }
    
    tt++
    stack[tt] = i
}

方式二:逆序写法

代码语言:go
复制
for i := n-1; i >= 0; i-- {
    
    for tt > 0 && nums[i] >= nums[stack[tt]] {
        tt--
    }
    
    val := -1
    if tt > 0 {
        // 当前nums[i]的右侧第一个比它大的元素是nums[stack[tt]]
        val = nums[stack[tt]]
    }
    ans[i] = val
    
    
    tt++
    stack[tt] = i
}

元素B右侧第一个比它小的元素

首先明确一下,使用单调增,顺序写或者逆序写都可以

代码语言:go
复制
for i := 0; i < n; i++ {
    
    for tt > 0 && nums[i] < nums[stack[tt]] {
        // 可以将nums[stack[tt]]作为元素B,右侧第一个比它小的元素就是nums[i]
        ans[stack[tt]] = nums[i]
        
        tt--
    }
    
    tt++
    stack[tt] = i
}

小结

  1. 综上,每个case都是可以使用顺序解决的,我建议使用顺序
  2. 第一个比它大,第一个比它小,对应的是栈的单调性;比它大,对应单调减;比它小,对应单调增;与右侧,还是左侧无关
  3. 比它大,或者大于等于,对应到代码中就是numsi与nums[stacktt]的大小关系中是否要加等号,这个可以先将代码写出来,然后再考虑
  4. 顺序或者逆序都是可以解决问题的,关键在于哪个是A,哪个是B,有一个相对关系,这个相对关系和顺序或逆序有关

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 什么是单调栈
  • 示例
    • 元素A左侧第一个比它大的元素
      • 元素A左侧第一个比它小的元素
        • 元素B右侧第一个比它大的元素
          • 元素B右侧第一个比它小的元素
          • 小结
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档