【算法题】2289. 使数组按非递减顺序排列

2023-03-15  本文已影响0人  程序员小2

题目:

给你一个下标从 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
解释:执行下述几个步骤:

输入:nums = [4,5,7,7,13]
输出:0
解释:nums 已经是一个非递减数组,因此,返回 0 。

提示:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

java代码:

class Solution {
    public int totalSteps(int[] nums) {
        var ans = 0;
        var st = new ArrayDeque<int[]>();
        for (var num : nums) {
            var maxT = 0;
            while (!st.isEmpty() && st.peek()[0] <= num)
                maxT = Math.max(maxT, st.pop()[1]);
            maxT = st.isEmpty() ? 0 : maxT + 1;
            ans = Math.max(ans, maxT);
            st.push(new int[]{num, maxT});
        }
        return ans;
    }
}

上一篇 下一篇

猜你喜欢

热点阅读