AI summary
type
status
date
slug
summary
category
tags
icon
password
本文给出单调栈模板的更多变形，后面讲的一些经典例题可以抽象成下面的这些标准场景，你到时候可以直接复制粘贴代码去解决。

单调栈模版的变体

下一个更大的元素

解释见上篇。这里直接贴代码如下：

下一个更大或相等的元素

本文给出这个问题的一些变体，比如说让你计算 nums[i] 的下一个大于等于 nums[i] 的元素怎么算？
其实很简单，把上面这段代码中 while 循环的 <= 号改成 < 号即可：

下一个更小的元素

也很简单，把之前实现的 nextGreaterElement 中 while 循环的 <= 条件改成 >= 条件即可得出下一个更小的元素：

上一个更大元素

注意之前我们的 for 循环都是从数组的尾部开始往栈里添加元素，这样栈顶元素就是 nums[i] 之后的元素。所以只要我们从数组的头部开始往栈里添加元素，栈顶的元素就是 nums[i] 之前的元素，即可计算 nums[i] 的上一个更大元素。
类似之前的几种实现，基于这个函数还可以求出 nums[i] 的上一个更大或相等的元素、上一个更小的元素、上一个更小或相等的元素，只要改一改 while 循环的符号即可。
至此，单调栈的几种标准模板就列举完了，他们之间有很多共性，理解性记忆就好，不用死记硬背。在实际算法题中不会直接考察你这些标准场景，但是稍加思考就可以抽象成这些标准场景。
下面带大家做几道习题练习一下单调栈模板的使用。

习题

1019. 链表中的下一个更大节点

给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
可以把链表转为数组存储，然后直接调用上面的 nextGreaterElement，略。
实际上 nextGreaterElement 也能从左到右遍历实现，维护一个内部值单调递减（不是严格单调递减，可以相等）的栈。栈中的元素对应着还没有找到下一个更大的元素的那些元素，它们在栈中的顺序与它们在数组中出现的顺序一致。这也解释了为什么栈中的值是单调递减的：如果有两个元素不满足单调递减的限制，那么后一个元素大于前一个元素，与「还没有找到下一个更大的元素」相矛盾。
当我们遍历到数组中值为 val 的元素时，只要它大于栈顶元素的值，我们就可以不断取出栈顶的节点，即栈顶节点的下一个更大的元素就是 val。在这之后，我们再将 val 放入栈顶，为其在后续的遍历中找到它的下一个更大的元素，同时也保证了栈的单调性。
将上面的模版函数改写为链表形式即可解本题，因为是链表，所以需要栈里需要记录一下索引。

1944. 队列中可以看到的人数

有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]) 。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
观察一下：
i 能看到它右边比它矮的一个递增序列(比如 )，以及第一个比它高的 j。
很明显是单调栈的题目，从后向前遍历，维护一个递减的栈，出栈的同时计数(上面所说的递增序列的长度)。

1475. 商品折扣后的最终价格

给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
就是计算下一个更小或相等的元素的模版：

901. 股票价格跨度

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
  • 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。
实现 StockSpanner 类：
  • StockSpanner() 初始化类对象。
  • int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。
相当于计算上一个更大的元素，记录索引，然后答案就是索引的差值。
注意，如果 stack 为空，说明没有上一个更大的元素，那么跨度就是从开始到当日。

402. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
如果想让结果尽可能小，那么清除数字分两步：
  1. 先删除 num 中的若干数字，使得 num 从左到右每一位都单调递增。比如 14329 转化成 129，这需要使用到单调栈。
  1. num 中的每一位变成单调递增的之后，如果 k 还大于 0（还可以继续删除）的话，则删除尾部的数字，比如 129 删除成 12。
第一条需要理解贪心的逻辑：
让我们从一个简单的例子开始。给定一个数字序列，例如 425，如果要求我们只删除一个数字，那么从左到右，我们有 4、2 和 5 三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始，2 小于它的左邻居 4。假设我们保留数字 4，那么所有可能的组合都是以数字 4（即 42，45）开头的。相反，如果移掉 4，留下 2，我们得到的是以 2 开头的组合（即 25），这明显小于任何留下数字 4 的组合。因此我们应该移掉数字 4。如果不移掉数字 4，则之后无论移掉什么数字，都不会得到最小数。
基于上述分析，我们可以得出「删除一个数字」的贪心策略：
给定一个长度为 n 的数字序列 ，从左往右找到第一个位置 i（i>0）使得 ，并删去 ；如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。
那么，为什么 一定要删其中一个呢？我留着删后面的不行吗？
不行，因为优先删高位才能得到最优，假设一下然后反证就明白了。假设留着 ，一定不是最优解，因为删掉它一定比留着它小(同一位数上 )。

853. 车队

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。
给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。
一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。
车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。
即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。
返回到达目的地的车队数量 。
这题考察「单调栈」结构的使用。是否能够形成车队，取决于下述规律：
如果车 x 排在 车 y 后面，且 x 到达终点所需时间比 y 少，则 x 必然会被 y 卡住，形成车队。
所以本题的思路是先根据每辆车的起始位置 position 排序，然后计算出时间数组 time。
假设计算出的 time 数组为 [12, 3, 7, 1, 2]，那么观察数组的单调性变化，最后肯定会形成三个车队，他们到达终点的时间分别是 12, 7, 2。
可以利用单调栈结构模拟得出结果，不过效率稍微低一些。也可以倒序遍历数组得出递增子序列，子序列的个数即答案。

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
最简单的解法是排序，排序之后很容易看出来哪一部分子数组乱序了。这里主要介绍一下单调栈的解法。
单调递增栈会筛选出递增的元素序列，换句话说，每加入一个新元素 x，就会弹出栈顶大于 x 的其他元素，直到栈顶元素小于 x 为止。
反过来，单调递减栈会筛选出递减的元素序列，换句话说，每加入一个新元素 x，就会弹出栈顶小于 x 的其他元素，直到栈顶元素大于 x 为止。
综上，如果正序遍历 nums，维护一个递增栈，那么弹出的元素就是乱序的元素；如果反向遍历 nums，维护一个递减栈，那么弹出的元素就是乱序的元素。