解题思路
本题可以使用单调栈解决。
对于每个元素 nums[i],我们需要判断它会在第几轮被删除。
从左到右遍历数组,维护一个单调递减趋势相关的栈,栈中保存:
P4902.使数组按非递减顺序排列
题目描述
给定一个长度为 n 的整数数组 nums。
在一步操作中,需要同时移除所有满足 nums[i−1]>nums[i] 的元素 nums[i],其中 1<=i<n。
重复执行上述操作,直到数组 nums 变为非递减数组。
请输出使数组变为非递减数组所需执行的操作次数。
输入描述
第一行输入一个整数 n,表示数组 nums 的长度。
第二行输入 n 个整数,表示数组 nums 中的元素。
输出描述
输出一个整数,表示使数组 nums 变为非递减数组所需执行的操作次数。
样例 1
输入
11
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
输入
5
4 5 7 7 13
输出
0
解释
nums 已经是一个非递减数组,因此,输出 0。
数据范围
- 1<=n<=105
- 1<=nums[i]<=109