【练习】单调栈的几种变体及经典习题

单调栈模板的变体

下一个更大的元素

上篇文章 单调栈的实现 带你使用单调栈解决了「下一个更大元素」的问题，比如下面这个例子：

输入：nums = [1, 3, 2, 4, 4]
返回：res = [3, 4, 4, -1, -1]

我们实现了这样一个函数解决这个问题：

// 计算 nums 中每个元素的下一个更大元素
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    // 因为是求 nums[i] 后面的元素，所以倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 删掉 nums[i] 后面较小的元素
        while (!stk.isEmpty() && stk.peek() <= nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 身后的更大元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

下一个更大或相等的元素

本文给出这个问题的一些变体，比如说让你计算 nums[i] 的下一个大于等于 nums[i] 的元素怎么算？比如下面这个例子：

输入：nums = [1, 3, 2, 4, 4]
返回：res = [3, 4, 4, 4, -1]

其实很简单，把上面这段代码中 while 循环的 <= 号改成 < 号即可：

// 计算 nums 中每个元素的下一个更大或相等的元素
int[] nextGreaterOrEqualElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    for (int i = n - 1; i >= 0; i--) {
        // 把这里改成 < 号
        while (!stk.isEmpty() && stk.peek() < nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 身后的大于等于 nums[i] 的元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

下一个更小的元素

再变一变，如果让你计算 nums[i] 的下一个小于 nums[i] 的元素，怎么算？比如下面这个例子：

输入：nums = [8, 4, 6, 6, 3]
返回：res = [4, 3, 3, 3, -1]

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

// 计算 nums 中每个元素的下一个更小的元素
int[] nextLessElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 删掉 nums[i] 后面较大的元素
        while (!stk.isEmpty() && stk.peek() >= nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 身后的更小元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

下一个更小或相等的元素

如果让你计算 nums[i] 的下一个小于或等于 nums[i] 的元素，怎么算？比如下面这个例子：

输入：nums = [8, 4, 6, 6, 3]
返回：res = [4, 3, 6, 3, -1]

类似的，把 nextLessElement 函数的 while 循环中的 >= 改成 > 即可：

// 计算 nums 中每个元素的下一个更小或相等的元素
int[] nextLessOrEqualElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>();
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 删掉 nums[i] 后面较大的元素
        while (!stk.isEmpty() && stk.peek() > nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 身后的更小或相等元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

上一个更大元素

之前的 4 个例子都是计算 nums[i] 的下一个更大/更小元素，现在请你计算 nums[i] 的上一个更大元素，你会不会？比如这个例子：

输入：nums = [8, 7, 6, 7]
返回：res = [-1, 8, 7, 8]

注意之前我们的 for 循环都是从数组的尾部开始往栈里添加元素，这样栈顶元素就是 nums[i] 之后的元素。所以只要我们从数组的头部开始往栈里添加元素，栈顶的元素就是 nums[i] 之前的元素，即可计算 nums[i] 的上一个更大元素。

代码实现如下：

// 计算 nums 中每个元素的上一个更大元素
int[] prevGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    // 因为是求 nums[i] 前面的元素，所以正着往栈里放
    for (int i = 0; i < n; i++) {
        // 删掉 nums[i] 前面较小的元素
        while (!stk.isEmpty() && stk.peek() <= nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 前面的更大元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

类似之前的几种实现，基于这个函数还可以求出 nums[i] 的上一个更大或相等的元素、上一个更小的元素、上一个更小或相等的元素，只要改一改 while 循环的符号即可，下面一一列出具体实现。

上一个更大或相等的元素

举例：

输入：nums = [8, 7, 6, 7]
返回：res = [-1, 8, 7, 8]

代码实现：

// 计算 nums 中每个元素的上一个更大或相等元素
int[] prevGreaterOrEqualElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    for (int i = 0; i < n; i++) {
        // 注意不等号
        while (!stk.isEmpty() && stk.peek() < nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 前面的更大或相等元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

上一个更小的元素

举例：

输入：nums = [3, 6, 6, 5]
返回：res = [-1, 3, 3, 3]

代码实现：

// 计算 nums 中每个元素的上一个更小的元素
int[] prevLessElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    for (int i = 0; i < n; i++) {
        // 把 nums[i] 之前的较大元素删除
        while (!stk.isEmpty() && stk.peek() >= nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 前面的更小元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

上一个更小或相等的元素

举例：

输入：nums = [3, 6, 6, 5]
返回：res = [-1, 3, 6, 3]

代码实现：

// 计算 nums 中每个元素的上一个更小或相等元素
int[] prevLessOrEqualElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> stk = new Stack<>(); 
    for (int i = 0; i < n; i++) {
        // 注意不等号
        while (!stk.isEmpty() && stk.peek() > nums[i]) {
            stk.pop();
        }
        // 现在栈顶就是 nums[i] 前面的更小或相等元素
        res[i] = stk.isEmpty() ? -1 : stk.peek();
        stk.push(nums[i]);
    }
    return res;
}

至此，单调栈的几种标准模板就列举完了，他们之间有很多共性，理解性记忆就好，不用死记硬背。在实际算法题中不会直接考察你这些标准场景，但是稍加思考就可以抽象成这些标准场景。

下面带大家做几道习题练习一下单调栈模板的使用。

习题

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

1019. 链表中的下一个更大节点 | 力扣 | LeetCode |  🟠

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：

• 链表中节点数为 n
• 1 <= n <= 104
• 1 <= Node.val <= 109

题目来源：力扣 1019. 链表中的下一个更大节点。

基本思路

这道题输入的是一条单链表，我们把它转化成数组，方便用索引访问即可直接套用 单调栈模板 中的 nextGreaterElement 函数逻辑。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        # 把单链表转化成数组，方便通过索引访问
        nums = []
        p = head
        while p:
            nums.append(p.val)
            p = p.next
        
        # 存放答案的数组
        res = [0] * len(nums)
        stk = []
        
        # 单调栈模板，求下一个更大元素，从后往前遍历
        for i in range(len(nums) - 1, -1, -1):
            while stk and stk[-1] <= nums[i]:
                stk.pop()
            # 本题要求没有下一个更大元素时返回 0
            res[i] = 0 if not stk else stk[-1]
            stk.append(nums[i])
        
        return res

可视化

 算法可视化面板

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

1944. 队列中可以看到的人数 | 力扣 | LeetCode |  🔴

有 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 个人在他右侧队列中能 看到 的 人数 。

示例 1：

输入：heights = [10,6,8,5,11,9]
输出：[3,1,2,1,1,0]
解释：
第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。

示例 2：

输入：heights = [5,1,2,3,10]
输出：[4,1,1,1,0]

提示：

• n == heights.length
• 1 <= n <= 105
• 1 <= heights[i] <= 105
• heights 中所有数 互不相同 。

题目来源：力扣 1944. 队列中可以看到的人数。

基本思路

这道题显然要用到 单调栈技巧：靠左的高个子可以把靠右相邻的矮个子都「挤掉」，相当于计算下一个更大元素，即 单调栈的几种模板实现 中的 nextGreaterElement 函数。

只不过这道题不是问你下一个更大元素是多少，而是问你当前元素和下一个更大元素之间的元素个数，直接看解法代码吧。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

class Solution:
    def canSeePersonsCount(self, heights):
        n = len(heights)
        res = [0] * n
        # int[] 记录 {身高，小于等于该身高的人数} 二元组
        stk = []
        for i in range(n - 1, -1, -1):
            # 记录右侧比自己矮的人
            count = 0
            # 单调栈模板，计算下一个更大或相等元素（身高）
            while stk and heights[i] > stk[-1]:
                stk.pop()
                count += 1
            # 不仅可以看到比自己矮的人，如果后面存在更高的的人，也可以看到这个高人
            res[i] = count if not stk else count + 1
            stk.append(heights[i])
        return res

可视化

 算法可视化面板

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

1475. 商品折扣后的最终价格 | 力扣 | LeetCode |  🟢

给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。

商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。

请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

示例 1：

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。

示例 2：

输入：prices = [1,2,3,4,5]
输出：[1,2,3,4,5]
解释：在这个例子中，所有商品都没有折扣。

示例 3：

输入：prices = [10,1,1,6]
输出：[9,0,1,6]

提示：

• 1 <= prices.length <= 500
• 1 <= prices[i] <= 10^3

题目来源：力扣 1475. 商品折扣后的最终价格。

基本思路

这道题就用到了 单调栈的几种模板实现 中讲到的一个单调栈模板：计算下一个更小或相等的元素。我是为了运用模板，所以把解法分成了两个函数，效率可能会降低一些，你完全可以优化这个解法的形式，使之更高效。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        res = [0] * n
        # 下一个小于等于 price[i] 的价格就是优惠券折扣
        next_element = self.nextLessOrEqualElement(prices)
        for i in range(len(prices)):
            # 如果存在优惠券，则减少相应的价格
            if next_element[i] != -1:
                res[i] = prices[i] - next_element[i]
            else:
                res[i] = prices[i]
        return res

    # 单调栈模板：计算 nums 中每个元素的下一个更小或相等的元素
    def nextLessOrEqualElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 存放答案的数组
        res = [-1] * n
        s = []
        # 倒着往栈里放
        for i in range(n - 1, -1, -1):
            # 删掉 nums[i] 后面较大的元素
            while s and s[-1] > nums[i]:
                s.pop()
            # 现在栈顶就是 nums[i] 身后的更小或相等元素
            res[i] = s[-1] if s else -1
            s.append(nums[i])
        return res

可视化

 算法可视化面板

901. 股票价格跨度

901. 股票价格跨度 | 力扣 | LeetCode |  🟠

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

• 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

• StockSpanner() 初始化类对象。
• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

示例：

输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85);  // 返回 6

 

提示：

• 1 <= price <= 105
• 最多调用 next 方法 104 次

题目来源：力扣 901. 股票价格跨度。

基本思路

这道题显然要用到 单调栈技巧：当加入 price 时，把所有小于等于 price 的价格都「挤掉」，相当于计算前一个更大元素，即 单调栈的几种模板实现 中的 prevGreaterElement 函数。

比如已经入栈的价格序列是 [40, 30, 20, 10]，那么如果执行 next(25)，价格序列变成 [40, 30, 25]，20 和 10 都会被「挤掉」，算上 25 本身，函数返回 2 + 1 = 3。

但还有个问题，这个 3 应该作为「权重」和 25 一同存储在栈中。因为之后 25 还可能被挤掉，比如说执行 next(26)，价格序列就变成了 [40, 30, 26]，但这种情况下之前的 20 和 10 显然也应该被挤掉，函数应该返回 3 + 1 = 4。具体解法看代码吧。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

class StockSpanner:
    # int[] 记录 {价格，小于等于该价格的天数} 二元组
    def __init__(self):
        self.stk = []

    def next(self, price: int) -> int:
        # 算上当天
        count = 1
        # 单调栈模板
        while self.stk and price >= self.stk[-1][0]:
            # 挤掉价格低于 price 的记录
            prev = self.stk.pop()
            # 计算小于等于 price 的天数
            count += prev[1]
        self.stk.append([price, count])

        return count

402. 移掉 K 位数字

402. 移掉 K 位数字 | 力扣 | LeetCode |  🟠

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。

提示：

• 1 <= k <= num.length <= 105
• num 仅由若干位数字（0 - 9）组成
• 除了 0 本身之外，num 不含任何前导零

题目来源：力扣 402. 移掉 K 位数字。

基本思路

如果想让结果尽可能小，那么清除数字分两步：

1、先删除 num 中的若干数字，使得 num 从左到右每一位都单调递增。比如 14329 转化成 129，这需要使用到 单调栈技巧。

2、num 中的每一位变成单调递增的之后，如果 k 还大于 0（还可以继续删除）的话，则删除尾部的数字，比如 129 删除成 12。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stk = []
        for c in num:
            # 单调栈代码模板
            while stk and k > 0 and c < stk[-1]:
                stk.pop()
                k -= 1
            # 防止 0 作为数字的开头
            if not stk and c == '0':
                continue
            stk.append(c)

        # 此时栈中元素单调递增，若 k 还没用完的话删掉栈顶元素
        final_stack = stk[:-k] if k else stk

        # 将栈中字符转化成字符串
        # 出栈顺序和字符串顺序是反的
        result = ''.join(final_stack).lstrip('0')

        # 若最后没剩下数字，就是 0
        return result if result else '0'

可视化

 算法可视化面板

853. 车队

853. 车队 | 力扣 | LeetCode |  🟠

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。

给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。

车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。

即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。

返回到达目的地的车队数量 。

示例 1：

输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

输出：3

解释：

• 从 10（速度为 2）和 8（速度为 4）开始的车会组成一个车队，它们在 12 相遇。车队在 target 形成。
• 从 0（速度为 1）开始的车不会追上其它任何车，所以它自己是一个车队。
• 从 5（速度为 1） 和 3（速度为 3）开始的车组成一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

示例 2：

输入：target = 10, position = [3], speed = [3]

输出：1

解释：

只有一辆车，因此只有一个车队。

示例 3：

输入：target = 100, position = [0,2,4], speed = [4,2,1]

输出：1

解释：

• 从 0（速度为 4） 和 2（速度为 2）开始的车组成一个车队，在 4 相遇。从 4 开始的车（速度为 1）移动到了 5。
• 然后，在 4（速度为 2）的车队和在 5（速度为 1）的车成为一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

提示：

• n == position.length == speed.length
• 1 <= n <= 105
• 0 < target <= 106
• 0 <= position[i] < target
• position 中每个值都 不同
• 0 < speed[i] <= 106

题目来源：力扣 853. 车队。

基本思路

这题考察「单调栈」结构的使用。是否能够形成车队，取决于下述规律：

如果车 x 排在 车 y 后面，且 x 到达终点所需时间比 y 少，则 x 必然会被 y 卡住，形成车队。

所以本题的思路是先根据每辆车的起始位置 position 排序，然后计算出时间数组 time。

假设计算出的 time 数组为 [12, 3, 7, 1, 2]，那么观察数组的单调性变化，最后肯定会形成三个车队，他们到达终点的时间分别是 12, 7, 2。

可以利用单调栈结构模拟得出结果，不过效率稍微低一些。也可以倒序遍历数组得出递增子序列，子序列的长度即答案。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        n = len(position)
        cars = []
        for i in range(n):
            cars.append([position[i], speed[i]])
        # 按照初始位置，从小到大排序
        cars.sort(key=lambda x: x[0])
        # 计算每辆车到达终点的时间
        time = []
        for i in range(n):
            car = cars[i]
            time.append((target - car[0]) / car[1])
        
        # 使用单调栈计算车队的数量
        # (This part is commented out in the original Java code, so it's also commented out here)
        # stk = []
        # for t in time:
        #     while stk and t >= stk[-1]:
        #         stk.pop()
        #     stk.append(t)
        # return len(stk)

        # 避免使用栈模拟，倒序遍历取递增序列就是答案
        res = 0
        max_time = 0
        for i in range(n - 1, -1, -1):
            if time[i] > max_time:
                max_time = time[i]
                res += 1
        return res

可视化

 算法可视化面板

581. 最短无序连续子数组

581. 最短无序连续子数组 | 力扣 | LeetCode |  🟠

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

提示：

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

题目来源：力扣 581. 最短无序连续子数组。

基本思路

最简单的解法是排序，排序之后很容易看出来哪一部分子数组乱序了。这里主要介绍一下单调栈的解法。

单调递增栈会筛选出递增的元素序列，换句话说，每加入一个新元素 x，就会弹出栈顶大于 x 的其他元素，直到栈顶元素小于 x 为止。

反过来，单调递减栈会筛选出递减的元素序列，换句话说，每加入一个新元素 x，就会弹出栈顶小于 x 的其他元素，直到栈顶元素大于 x 为止。

综上，如果正序遍历 nums，维护一个递增栈，那么弹出的元素就是乱序的元素；如果反向遍历 nums，维护一个递减栈，那么弹出的元素就是乱序的元素。

详细题解：

• 【练习】单调栈的几种变体及经典习题

解法代码

# 排序解法
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        temp = sorted(nums)
        left = float('inf')
        right = float('-inf')
        for i in range(len(nums)):
            if temp[i] != nums[i]:
                left = i
                break
        for i in range(len(nums) - 1, -1, -1):
            if temp[i] != nums[i]:
                right = i
                break
        if left == float('inf') and right == float('-inf'):
            # nums 本来就是有序的
            return 0
        return right - left + 1

# 单调栈解法
class Solution2:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = float('inf')
        right = float('-inf')
        # 递增栈，存储元素索引
        incr_stk = []
        for i in range(n):
            while incr_stk and nums[incr_stk[-1]] > nums[i]:
                # 弹出的元素都是乱序元素，其中最小的索引就是乱序子数组的左边界
                left = min(left, incr_stk.pop())
            incr_stk.append(i)
        # 递减栈，存储元素索引
        decr_stk = []
        for i in range(n - 1, -1, -1):
            while decr_stk and nums[decr_stk[-1]] < nums[i]:
                # 弹出的元素都是乱序元素，其中最大的索引就是乱序子数组的右边界
                right = max(right, decr_stk.pop())
            decr_stk.append(i)
        if left == float('inf') and right == float('-inf'):
            # 说明单调栈没有弹出任何元素，即 nums 本来就是有序的
            return 0
        return right - left + 1