社区首页 >专栏 >单调栈，好难。。。

单调栈，好难。。。

五分钟学算法

发布于 2023-09-09 09:56:36

24400

代码可运行

文章被收录于专栏：五分钟学算法五分钟学算法

运行总次数：0

代码可运行

我给出了一个结论，基本上单调栈的代码 80% 都是类似下方的样子。

for 从左向右
  while stack and stack[-1] > xx :
       逻辑操作
    
    stack.append(xx)

在 LeetCode 1475、商品折扣后的最终价格 一题中，我写的代码是从右向左遍历的。

在 LeetCode 739、每日温度 一题中，我写的的代码是从左向右遍历的。

这个时候，有个同学提出一个疑问：

实际上，单调栈的题目无论是从左向右还是从右向左遍历数组都是可以的，代码框架类似，我们以一道大厂真题来具体解释一下正序和逆序的一个区别。

题目描述

在学校中，N个小朋友站成一队，第i个小朋友的身高为height[i]，第i个小朋友可以看到的右边的第一个比自己身高更高的小朋友j，那么j是i的好朋友（j > i）。请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。小朋友人数范围是 [0, 40000]。

输入描述

第一行输入N，表示有N个小朋友

第二行输入N个小朋友的身高height[i]，都是整数

输出描述

输出N个小朋友的好朋友的位置

示例一

输入

2
100 95

输出

0 0

示例二

输入

8
123 124 125 121 119 122 126 123

输出

1 2 6 5 5 6 0 0

解题思路

注意，本题和LC739. 每日温度非常类似。区别在于，本题需要找到的是右边下一个更大元素的索引，而非与当前元素的间隔，显然变得更加简单了。

我们讲过，类似这种要求寻找左边/右边最近的更大/更小元素的题目，均可以使用单调栈来完成。

对于单调栈的题目，既可以正序遍历也可以逆序遍历数组来完成，重点在于理解单调栈的原理，同学们只需要选择适合自己理解的方法来完成即可。以下表格总结了两种不同遍历顺序的异同点。

	正序遍历	逆序遍历
单调栈顺序	栈中储存的索引所对应在原数组中的元素大小，从栈底至栈顶单调递减，即更大的数（的下标）位于栈底
入栈时机	栈顶元素反复出栈并修改ans之后，进行入栈。且入栈元素为当前下标i，而非身高h
修改ans时机	i为preIndex的下一个更大元素的下标，在出栈过程中，即在while内修改ans[preIndex]	stack[-1]为i的下一个更大元素的下标，在出栈结束后，即在while外修改ans[i]
出栈条件	h > height[stack[-1]]	h >= height[stack[-1]]

代码

解法一

正序遍历height构建单调栈。

# 输入小朋友个数n
n = int(input())
# 输入N个小朋友的高度数组
height = list(map(int, input().split()))

# 构建一个单调栈，用来存放不同小朋友的身高的索引
# 栈中储存的索引所对应在height中的元素大小，从栈底至栈顶单调递减
# 即更大的数（的下标）位于栈底
stack = list()

# 构建列表ans，用来保存输出结果
# 初始化其中所有的元素均为0
ans = [0] * n

# 从头开始遍历每一个小朋友的身高
for i, h in enumerate(height):
    # 第i个小朋友的身高h，需要不断地与栈顶元素比较
    # 如果栈顶元素存在并且h【大于】栈顶元素stack[-1]
    # 意味着栈顶元素找到了右边最近的比他更高的身高h
    while len(stack) > 0 and h > height[stack[-1]]:
        # 首先获取栈顶元素的值，也就是上一个比h小的身高的索引值
        preIndex = stack.pop()

        # i即为preIndex这个索引所对应的，下一个最近身高
        ans[preIndex] = i

    # 再把当前小朋友身高的下标i存放到栈中
    # 注意：所储存的是下标i，而不是身高h
    stack.append(i)

# ans中的int元素转成str后才能合并成字符串
print(" ".join(map(str, ans)))

解法二

逆序遍历height构建单调栈。

# 输入小朋友个数n
n = int(input())
# 输入N个小朋友的高度数组
height = list(map(int, input().split()))

# 构建一个单调栈，用来存放不同小朋友的身高的索引
# 栈中储存的索引所对应在height中的元素大小，从栈底至栈顶单调递增
# 即更大的数（的下标）位于栈底
stack = list()

# 构建列表ans，用来保存输出结果
# 初始化其中所有的元素均为0
ans = [0] * n

# 逆序遍历每一个小朋友的身高
for i in range(n-1, -1, -1):
    h = height[i]
    # 第i个小朋友的身高h，需要不断地与栈顶元素比较
    # 如果栈顶元素存在并且h【大于等于】栈顶元素stack[-1]
    # 说明栈顶元素stack[-1]并不是身高h右边最近的比h更大的元素
    # 需要将栈顶元素弹出，继续寻找比h大的栈顶元素
    while len(stack) > 0 and h >= height[stack[-1]]:
        # 栈顶元素下标对应的身高不大于当前身高h，不是符合要求的更大身高，弹出
        stack.pop()
    # 完成弹出后，如果栈顶仍存在元素，说明stack[-1]所对应的身高，是严格比h大的下一个身高
    if len(stack) > 0:
        # ans[i]修改为stack[-1]
        ans[i] = stack[-1]

    # 再把当前小朋友身高的下标i存放到栈中
    # 注意：所储存的是下标i，而不是身高h
    stack.append(i)

# ans中的int元素转成str后才能合并成字符串
print(" ".join(map(str, ans)))