单调栈题目：找出最具竞争力的子序列

题目

标题和出处

标题：找出最具竞争力的子序列

出处：1673. 找出最具竞争力的子序列

难度

6 级

题目描述

要求

给你一个整数数组 $\text{nums}$ 和一个正整数 $\text{k}$，返回 $\text{nums}$ 的长度为 $\text{k}$ 且最具竞争力的子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 $\text{a}$ 和子序列 $\text{b}$ 第一个不相同的位置上，如果 $\text{a}$ 中的数字小于 $\text{b}$ 中对应的数字，那么我们称子序列 $\text{a}$ 比子序列 $\text{b}$（相同长度下）更具竞争力。 例如，$\text{[1,3,4]}$ 比 $\text{[1,3,5]}$ 更具竞争力，在第一个不相同的位置，也就是最后一个位置上，$\text{4}$ 小于 $\text{5}$。

示例

示例 1：

输入：$\text{nums = [3,5,2,6], k = 2}$
输出：$\text{[2,6]}$
解释：在所有可能的子序列集合 $\text{{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}}$ 中，$\text{[2,6]}$ 最具竞争力。

示例 2：

输入：$\text{nums = [2,4,3,3,5,4,9,6], k = 4}$
输出：$\text{[2,3,3,4]}$

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{nums[i]}\le {\text{10}}^{\text{9}}$
• $\text{1}\le \text{k}\le \text{nums.length}$

解法

思路和算法

这道题中，竞争力顺序和字典序相似。要得到数组 $\text{nums}$ 的长度为 $k$ 的最具竞争力的子序列，等价于从数组 $\text{nums}$ 中删除 $\text{nums}.\text{length}-k$ 个元素，使得剩下的 $k$ 个元素形成的子序列是竞争力顺序最靠前的。记 $\text{remove}=\text{nums}.\text{length}-k$，则 $\text{remove}$ 是需要删除的元素个数。

基于上述分析，这道题和「移掉 K 位数字」相似。

如果只从数组 $\text{nums}$ 中删除一个元素，使得剩下的子序列为竞争力顺序最靠前，则应该使子序列中靠前的数字尽可能小。可能有两种情况，以下是两种情况和对应的策略：

1. 存在下标 $i$ 使得 $\text{nums}[i]>\text{nums}[i+1]$，则找到满足该要求的最小的下标 $i$，将下标 $i$ 处的元素删除之后，剩下的子序列为竞争力顺序最靠前；

2. 不存在下标 $i$ 使得 $\text{nums}[i]>\text{nums}[i+1]$，则将 $\text{nums}$ 的最后一个元素删除，剩下的子序列为竞争力顺序最靠前。

根据上述策略执行 $\text{remove}$ 次删除元素操作，得到的子序列即为最具竞争力的子序列。

由于数组 $\text{nums}$ 的长度最大为 $10^5$，因此模拟上述操作的做法会超出时间限制，需要优化。

由于上述策略优先考虑删除左边的元素，因此可以从左到右遍历 $\text{nums}$，在遍历过程中进行删除操作，只能删除 $\text{remove}$ 个元素。为了使得删除操作符合上述策略，可以使用单调栈，单调栈存储数字，满足从栈底到栈顶的数字单调递增。

从左到右遍历数组 $\text{nums}$，对于每个元素，进行如下操作：

1. 如果栈不为空、栈顶元素大于当前元素且已经删除的元素个数小于 $\text{remove}$，则将栈顶元素出栈，重复该操作直到上述条件不满足（三个条件之一不满足即停止）；

2. 将当前元素入栈。

遍历结束之后，如果已经删除的元素个数小于 $\text{remove}$，则需要继续删除元素，删除元素的方法是将栈顶元素出栈，直到删除的元素个数达到 $\text{remove}$。此时，栈内元素按照从栈底到栈顶的顺序构成的子序列为数组 $\text{nums}$ 的长度为 $k$ 的最具竞争力的子序列。

以下是示例 2 的计算过程，其中 $\text{num}=[2,4,3,3,5,4,9,6]$，$k=4$，需要删除的元素个数 $\text{remove}=4$。

1. 下标 $0$ 处的元素是 $2$，将 $2$ 入栈，$\text{stack}=[2]$，其中左边为栈底，右边为栈顶。

2. 下标 $1$ 处的元素是 $4$，将 $4$ 入栈，$\text{stack}=[2,4]$。

3. 下标 $2$ 处的元素是 $3$，由于 $4>3$，因此将 $4$ 出栈，将 $3$ 入栈，$\text{stack}=[2,3]$，共删除 $1$ 个元素。

4. 下标 $3$ 处的元素是 $3$，将 $3$ 入栈，$\text{stack}=[2,3,3]$，共删除 $1$ 个元素。

5. 下标 $4$ 处的元素是 $5$，将 $5$ 入栈，$\text{stack}=[2,3,3,5]$，共删除 $1$ 个元素。

6. 下标 $5$ 处的元素是 $4$，由于 $5>4$，因此将 $5$ 出栈，将 $4$ 入栈，$\text{stack}=[2,3,3,4]$，共删除 $2$ 个元素。

7. 下标 $6$ 处的元素是 $9$，将 $9$ 入栈，$\text{stack}=[2,3,3,4,9]$，共删除 $2$ 个元素。

8. 下标 $7$ 处的元素是 $6$，由于 $9>6$，因此将 $9$ 出栈，将 $6$ 入栈，$\text{stack}=[2,3,3,4,6]$，共删除 $3$ 个元素。

9. 遍历结束之后，还需要删除 $1$ 个元素才能得到长度为 $4$ 的子序列，因此将 $6$ 出栈，$\text{stack}=[2,3,3,4]$，共删除 $4$ 个元素。

10. 最具竞争力的子序列是 $[2,3,3,4]$。

代码

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int length = nums.length;
        int remove = length - k;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (!stack.isEmpty() && stack.peek() > num && remove > 0) {
                stack.pop();
                remove--;
            }
            stack.push(num);
        }
        while (remove > 0) {
            stack.pop();
            remove--;
        }
        int[] subsequence = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            subsequence[i] = stack.pop();
        }
        return subsequence;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要遍历数组 $\text{nums}$ 进行删除 $n-k$ 个元素的操作，由于每个元素最多入栈和出栈各一次，其中最多有 $n-k$ 个数字出栈，因此时间复杂度是 $O(n+(n-k))=O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。空间复杂度主要取决于栈空间，栈内元素个数不会超过 $n$。