美文网首页
【算法题】2289. 使数组按非递减顺序排列

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

作者: 程序员小2 | 来源:发表于2023-03-15 08:00 被阅读0次

题目:

给你一个下标从 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

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;
    }
}

相关文章

  • LeetCode 977. 有序数组的平方

    题目 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 ...

  • 【算法题】24.有序数组的平方

    题目 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 ...

  • 977. 有序数组的平方

    977. 有序数组的平方 给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺...

  • 有序数组的平方

    题目: 给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例: ...

  • [LeetCode][Python]977. 有序数组的平方

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1: 输入...

  • LeetCode-977-有序数组的平方

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。image.png...

  • 977. 有序数组的平方

    【题目描述】给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 【示...

  • 977. 有序数组的平方

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1: 输入...

  • 有序数组的平方

    题目描述 给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 ...

  • 有序数组的平方

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1: 输入...

网友评论

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

      本文链接:https://www.haomeiwen.com/subject/kiclrdtx.html