2289. 使数组按非递减顺序排列

Difficulty
Medium
Tags
单调栈
URL
https://leetcode.cn/problems/steps-to-make-array-non-decreasing/
Star
给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。
示例 1：
输出：3
解释：执行下述几个步骤：
- 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
- 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
- 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]
[5,7,11,11] 是一个非递减数组，因此，返回 3 。
示例 2：
输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是一个非递减数组，因此，返回 0 。
提示：
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

法1 单调栈

思路
每个数会将其右侧所有比自己小的数消去，直到碰到第一个不小于自己的数为止。找右侧首个不小于自己的数是单调栈的典型应用场景，所以启发我们从单调栈的做法入手。
我们考虑下面这个样例: [10,1,2,7,1,2,6,1,2,3,20] 可以先将其分成独立的四个区间来看： [10,1,2], [7,1,2], [6,1,2,3], [20] 每个区间最后都会消去到只剩首个数字，即： [10], [7], [6], [20] 其各自内部所需的消去次数分别为: 2, 2, 3, 0
完成了区间内部的消去之后，我们来考虑区间之间的消去情况，我们从右至左来依次考虑： [6], [20]这两个区间无法消除，因为6<20。 [7], [6]这两个区间可以进一步消除，因为7>6。接下来是重点，把这两个区间消除到只剩一个[7]，需要的时间是多少。区间[6]只用管自己内部的消除，而区间[7]除了自己内部消除外，还要把右边的6给消除掉，所以总时间为max(区间[7]的消除时间+1, 区间[6]的消除时间)=max(2+1, 3)=3。 所以现在我们的区间变成了: [10], [7], [20] 其各自内部所需的消去次数分别为: 2, 3, 0
同理，我们再考虑区间[10]和[7]的合并，最终区间变成了: [10], [20] 其各自内部所需的消去次数分别为: 3, 0
最终答案就是所剩区间的最大消去次数，即为3。
对应到代码中，就是从右至左遍历每个数，维护单调递减栈，并同时维护把右侧小的数都消去所需的时间。
题解
class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        stack = []
        res = 0
        for num in nums[::-1]:
            cnt = 0
            #cnt 为 将后面 小于 num 的数字都删掉 需要的 次数
            while len(stack) > 0 and num > stack[-1][0]:
                # 这里max的时候，只需要 cnt + 1，stack[-1][1]不能+1, 因为 satck[-1][0] 后面的次数 可能和 当前数字一起删除。
                # 例  [10,6,5,10,15]
                cnt = max(cnt+1, stack[-1][1])
                stack.pop()
            stack.append([num, cnt])

            res = max(res, cnt)

        return res