当前位置: 首页> 房产> 政策 > 单调栈,LeetCode 2289. 使数组按非递减顺序排列

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

时间:2025/7/13 5:27:29来源:https://blog.csdn.net/EQUINOX1/article/details/141649384 浏览次数:0次

一、题目

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
 ​
关键字:单调栈,LeetCode 2289. 使数组按非递减顺序排列

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: