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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/steps-to-make-array-non-decreasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

好几周了，第三题终于不水了，可惜没做出来，这个题只过了不到200人，第四题都快800了，不可思议。

看大佬说是cf上的原题，那边都是思维题，果然是我做不出来的题目…

不过，自己的思路其实也差的不是太多，很快就知道是用单调栈，但是差关键一步，不知如何确定每个数字移除的步骤和前面数的关系。

「这个」题解讲的很明白，关键就是%20%2B%201%7D#card=math&code=f%5Bi%5D%20%3D%20%5Cdisplaystyle%7B%5Cmax%28f%5Bj%2B1%5D%5Cdots%20f%5Bi-1%5D%29%20%2B%201%7D&id=eR4AR)这个式子。

代码

class Solution {
    public int totalSteps(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        // f[i]表示消除下标为i的数字所需的次数
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            // 当前数的消除一次，初始化为1，最少需要1次
            int g = 1;
            // 下标介于[j+1,i-1]的比自己小的数需要出栈，同时更新g
            while (stack.size() > 0 && nums[i] >= nums[stack.peek()]) {
                int k = stack.pop();
                g = Math.max(g, f[k] + 1);
            }
            // 当前下标入栈之前，如果栈为空，说明左边没有比自己大的元素，这种情况下不更新f[i]和ans
            if (stack.size() > 0) {
                f[i] = g;
                ans = Math.max(ans, f[i]);
            }
            stack.push(i);
        }
        return ans;
    }
}