单调栈记录

发表于 更新于 分类于 ， 本文字数： 536 阅读时长 ≈ 4 分钟
单调栈是一种有顺序的栈，能够解决一些特定的问题

简介

单调栈不是一种新的数据结构，它就是一个栈。但是它里面的元素是按顺序排的。

单调栈能够解决一类特定的问题，抽象的概括就是：

在一个数组中，每个元素想要找到在它左边或者右边第一个比他大/小的元素，此时可以用单调栈来解决

代码模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def find_next_larger(nums):
    '''寻找数组中每个元素右侧第一个比他大的
    其中，找不到就用-1替代；找到就用那个元素的下标。

    Args:
        nums: 一维数组

    Returns:
        返回一个对应长度的一维数组
    '''
    n = len(nums)
    mono_stack = [] # 存储当前比较大的元素的下标
    ans = [-1]*n
    for i in range(n):
        while mono_stack and nums[mono_stack[-1]] < nums[i]:
            # prev对应的元素是数组中左侧的元素，此时有一个右侧的元素比它大
            # 那这个元素就是prev对应的元素的右侧的第一个比它大的元素了
            prev = mono_stack.pop()
            ans[prev] = i
        mono_stack.append(i)
    return ans

参考资料

  1. OI Wiki的介绍