2289-使数组按非递减顺序排列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个下标从 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 <= 105
  • 1 <= nums[i] <= 109

本题 视频讲解 已出炉，欢迎点赞三连~

提示 1

元素 x 会被左边某个比他大的元素 y 给删除（如果存在的话）。

我们需要计算在删除 x 之前，删除了多少个比 y 小的元素，从而算出删除 x 的时刻（第几步操作）。

答案可以转换成所有（能被删除的）元素被删除的时刻的最大值。

提示 2

以 [20,1,9,1,2,3] 为例。

  • 时刻一 20 删掉 1，9 删掉 1；
  • 时刻二 20 删掉 9，9 删掉 2;
  • 时刻三 20 接替了 9 的任务，来删除数字 3。

虽然说数字 3 是被 20 删除的，但是由于 20 立马接替了 9，我们可以等价转换看作 3 是被 9 删除的，也就是它左边离它最近且比它大的那个数。

该等价转换不会影响数字被删除的时刻。

提示 3

再考虑这个例子 [9,1,2,3,4,1,5]。

5 应该被 9 删除。根据题目要求，在删除 5 之前，需要把 5 前面不超过 5 的元素都删除，然后才能删除 5。所以在删除 5 之前，我们需要知道 9 到 5 之间的所有元素被删除的时刻的最大值，这个时刻加一就是删除 5 的时刻。

这可以用单调栈 + 线段树来做，单调栈求左边最近更大元素位置，线段树维护区间最大值。（评论区 有人实现了这一思路）

但还有更巧妙的做法。

提示 4

对于一串非降的序列，该序列的每个元素被删除的时刻是单调递增的。（假设序列左侧有个更大的元素去删除序列中的元素）

利用这一单调性，我们只需要存储这串非降序列的最后一个元素被删除的时刻。

某一段区间会包含若干个非降序列，也就包含了若干个最后一个元素被删除的时刻，提示 3 中所需要计算的最大值必然在这些时刻中。

提示 5

我们可以用一个单调递减栈存储元素及其被删除的时刻，当遇到一个不小于栈顶的元素 x 时，就不断弹出栈顶元素，并取弹出元素被删除时刻的最大值，这样就得到了提示 3 中所需要计算的时刻的最大值 maxT。

然后将 x 及 maxT}+1 入栈。注意如果此时栈为空，说明前面没有比 x 大的元素，x 无法被删除，即 maxT}=0，这种情况需要将 x 及 0 入栈。

复杂度分析

  • 时间复杂度：O(n)。每个元素至多入栈出栈各一次。
  • 空间复杂度：O(n)。最坏情况下栈中有 n 个元素。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        ans, st = 0, []
        for num in nums:
            max_t = 0
            while st and st[-1][0] <= num:
                max_t = max(max_t, st.pop()[1])
            max_t = max_t + 1 if st else 0
            ans = max(ans, max_t)
            st.append((num, max_t))
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int totalSteps(vector<int> &nums) {
        int ans = 0;
        stack<pair<int, int>> st;
        for (int num : nums) {
            int maxT = 0;
            while (!st.empty() && st.top().first <= num) {
                maxT = max(maxT, st.top().second);
                st.pop();
            }
            maxT = st.empty() ? 0 : maxT + 1;
            ans = max(ans, maxT);
            st.emplace(num, maxT);
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func totalSteps(nums []int) (ans int) {
	type pair struct{ v, t int }
	st := []pair{}
	for _, num := range nums {
		maxT := 0
		for len(st) > 0 && st[len(st)-1].v <= num {
			maxT = max(maxT, st[len(st)-1].t)
			st = st[:len(st)-1]
		}
		if len(st) > 0 {
			maxT++
			ans = max(ans, maxT)
		} else {
			maxT = 0
		}
		st = append(st, pair{num, maxT})
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }
 Comments
On this page
2289-使数组按非递减顺序排列