力扣 6080. 使数组按非递减顺序排列

题目来源：https://leetcode.cn/problems/steps-to-make-array-non-decreasing/

大致题意：
给一个数组，移除所有满足 num[i - 1] > nums[i] 的 nums[i]，重复这个操作，直至没有满足条件的元素为止。返回需要的操作次数

---

思路

最后返回的数组会是一个升序数组，所以对于原数组的元素来说，若其左边有大于它的元素，那么它将会在某一次操作中被移除

统计每个元素被移除所需的操作次数，那么操作次数的最大值即为答案

设 i < j，nums[i] > nums[j]，若 i 与 j 之间的数不大于 nums[j]，那么只有在 i 与 j 之间所有的元素被移除后才会移除 nums[j]，于是 nums[j] 被移除的操作次数即为i 与 j 之间元素被移除所需的最大操作次数 + 1

于是可以使用单调栈维护一个递减序列，序列每个元素是数组的元素值和对应元素被移除所需的操作次数（栈底元素左侧没有更大值，不会被移除，对应操作次数为 0）

对于遍历到的每个元素

1. 若栈顶元素对应的数组元素值不大于当前元素，则弹出栈顶元素，并记录对应操作次数的最大值
2. 重复这个操作，直至栈顶元素对应的数组元素值大于当前元素或者栈为空（栈为空表示当前元素左侧没有比它更大的值）
3. 然后将当前元素和所需的操作次数（若栈为空，操作次数为 0；否则，操作次数为统计到的操作次数 + 1）入栈

最后答案即为遍历过程中统计的操作次数的最大值

代码：

 public int totalSteps(int[] nums) {
        // 单调栈
        Deque<int[]> stack = new ArrayDeque<>();
        int ans = 0;
        int n = nums.length;
        for (int num : nums) {
            // 当前元素被移除所需的操作次数
            int cur = 0;
            // 若栈不为空，且栈顶元素对应数组元素值不大于当前元素，栈顶出栈
            while (!stack.isEmpty() && stack.peek()[0] <= num) {
                // 统计出栈元素操作次数的最大值
                cur = Math.max(stack.pop()[1], cur);
            }
            // 若栈为空，当前元素不会被移除，操作次数为 0
            // 否则，当前元素被移除所需的操作次数即为统计的最大值 + 1
            cur = stack.isEmpty() ? 0 : cur + 1;
            // 当前元素和对应操作次数入栈
            stack.push(new int[]{num, cur});
            // 统计操作次数的最大值
            ans = Math.max(ans, cur);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23