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

题目

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。

重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。

示例 1：

输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
输出：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 <= 10^5
• 1 <= nums[i] <= 10^9

解答

思路

步骤就是时刻，我们可以看作每一个时刻 t 都会去掉一些元素，因此我们可以定义一个数组，它对应表示 nums[i] 是在什么时刻被去掉的：

nums = [9, 1, 2, 3, 1, 5]

outs = [N, 1, N, N, 1, N] # t = 1, nums = [9, 2, 3, 5]
outs = [N, 1, 2, N, 1, N] # t = 2, nums = [9, 3, 5]
outs = [N, 1, 2, 3, 1, N] # t = 3, nums = [9, 5]
outs = [N, 1, 2, 3, 1, 4] # t = 4, nums = [9]

如果某一轮没有任何数被去掉，那么这个数组一定已经是非递减序列了，因为它的任何一个 i 都满足 nums[i - 1] <= nums[i]。于是我们的答案为 max(outs) = 4。

第一眼：是不是可以找到一个递增序列，然后递增序列的元素被删除时间也是递增的呢？但是我们只能知道它是递增的，而分析不出来具体是哪个时刻被删除的，比如 nums[5] = 5，它是在 t = 4 时也就是第四轮被删掉的。

如果出现这样一种情况：nums = [20, 1, 9, 1, 2, 3, 1, 5]，那么 20 会先把 9 删掉，然后 20 再把 3 删掉。但我们可以认为 依然 是 9 在 t = 3 时刻删掉了 3，因为第二轮虽然删掉了 9，但是 20 马上上来顶替了它的位置，因而不会导致时间延后。

于是我们可以看作每一个数 nums[i] 都是 被它左边第一个比它大的数删掉的，虽然可能实际情况不是这样：

• 上一个更大的数在它之前就被删掉了，那么一定有更大的数接替了它的位置
• 上一个更大的数在它之前没被删掉，那么就是它删掉的

因此直观做法是：

• 单调栈求出每个数 nums[i] 左边离它最近且比它大的数下标 j
• 线段树求出 outs(i...j) 中的最大值 t，说明在 t 时刻 outs(i...j) 已经被清空
• 因此 outs[i] = t + 1

代码

class Solution:
    def totalSteps(self, nums: List[int]) -> int:

思路：简单做法