单调栈，LeetCode 2289. 使数组按非递减顺序排列

一、题目

1、题目描述

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

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

2、接口描述

python3

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

3、原题链接

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

---

二、解题报告

1、思路分析

被删除的数字会被左边某个比他大的数字删除

答案是最晚被删除的数字

我们考虑维护单调递减栈

如果数字小于栈顶，那么他的删除时刻为栈顶删除时刻+1

如果弹栈，那么我们维护弹栈过程中的最大删除时刻

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

python3

class Solution:def totalSteps(self, nums: List[int]) -> int:res = 0st = []for x in nums:ma = 0while st and st[-1][0] <= x:ma = max(ma, st.pop()[1])ma = ma + 1 if st else 0res = max(res, ma)st.append((x, ma))return res

 ​