解题思路

本题可以使用单调栈解决。

对于每个元素 $nums[i]$，我们需要判断它会在第几轮被删除。

从左到右遍历数组，维护一个单调递减趋势相关的栈，栈中保存：

• 元素值

题目描述

给定一个长度为 $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 <= 10^5$
• $1 <= nums[i] <= 10^9$