谁还不会单调栈

原创

marsxingzhi

发布于 2023-07-13 11:27:19

2270

发布于 2023-07-13 11:27:19

文章被收录于专栏：marsxingzhi的小天地

什么是单调栈

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

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

代码格式如下：

var stack []int
var tt int 

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

示例

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

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

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左侧第一个比它小的元素

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

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，由于固定的元素不同，因此逻辑写在不同的地方，一个是在回退栈的过程中处理，一个是在回退栈之后处理。

方式一：顺序写法

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
}

方式二：逆序写法

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右侧第一个比它小的元素

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

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
}