题目:
给你一个整数数组 nums
和一个正整数 k
,返回长度为 k
且最具 竞争力 的 nums
子序列。
数组的子序列是从数组中删除一些元素(可能不删除元素)得到的序列。
在子序列 a
和子序列 b
第一个不相同的位置上,如果 a
中的数字小于 b
中对应的数字,那么我们称子序列 a
比子序列 b
(相同长度下)更具 竞争力 。 例如,[1,3,4]
比 [1,3,5]
更具竞争力,在第一个不相同的位置,也就是最后一个位置上, 4
小于 5
。
示例 1:
输入:nums = [3,5,2,6], k = 2 输出:[2,6] 解释:在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中,[2,6] 最具竞争力。
示例 2:
输入:nums = [2,4,3,3,5,4,9,6], k = 4 输出:[2,3,3,4]
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length
解析:
这道题的关键在于找到最具竞争力的子序列,竞争力的定义是基于字典序列较小。
示例 1:
输入:nums = [3,5,2,6], k = 2
- 初始状态,栈为空。
- 处理元素3,当前栈:
- 处理元素5,当前栈:
- 处理元素2,栈中元素5大于2且可以弹出,因为有足够元素来保持序列长度2,当前栈:
- 处理元素6,当前栈:
输出:[2, 6]
示例 2:
输入:nums = [2,4,3,3,5,4,9,6], k = 4
- 初始状态,栈为空。
- 处理元素2,当前栈:
- 处理元素4,当前栈:
- 处理元素3,栈中元素4大于3且可以弹出,当前栈:
- 处理元素3,当前栈:
- 处理元素5,当前栈:
- 处理元素4,当前栈:
- 处理元素9,当前栈已满。
- 处理元素6,当前栈已满。
输出:[2, 3, 3, 4]
思路:
我们可以使用单调栈的方式来解决这个问题。具体来说,使用一个栈来保存子序列的元素,我们通过遍历原数组,对于每个元素进行判断:
- 当前元素是否应该被加入到栈中;
- 如果是,则判断栈顶元素是否应该被移除:
- 条件是栈顶元素大于当前元素,并且移除栈顶元素后仍可以从剩下的元素中构建长度为
k
的子序列。
- 条件是栈顶元素大于当前元素,并且移除栈顶元素后仍可以从剩下的元素中构建长度为
具体步骤如下:
- 初始化一个栈用于构建结果子序列;
- 遍历数组
nums
的每一个元素,根据条件进行判断和操作:- 当前栈的长度加上剩余未处理的元素数量大于等于
k
; - 如果栈顶元素大于当前元素,则可以将栈顶元素移除,以便让当前元素入栈;
- 将当前元素压入栈,且确保不超过
k
的长度;
- 当前栈的长度加上剩余未处理的元素数量大于等于
- 最终栈中的前
k
个元素即为答案。
知识点解析及代码实现:
知识点1:子序列与子数组
子序列是从数组中删除一些(或不删除)元素后得到的序列,其保留元素相对顺序。而子数组是数组中连续的一段。
知识点2:单调栈
单调栈是一种特定的栈,用来解决范围内最大、最小值问题。在这个问题中,单调栈用于维护一个递增的序列,确保竞争力。
知识点3:复杂度分析
时间复杂度:O(n),因为需要遍历数组一次,并且每个元素最多进栈一次、出栈一次;
空间复杂度:O(k),用于存储结果的栈最多存储 k 个元素。
代码实现:
import java.util.*;
class Solution {
public int[] mostCompetitive(int[] nums, int k) {
// 结果数组,长度为k
int[] result = new int[k];
// 栈顶指针,从0开始
int top = 0;
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 如果栈不空,且栈顶元素大于当前元素,且删除栈顶元素后剩余元素还能构成长度为k的子序列
while (top > 0 && result[top - 1] > nums[i] && top - 1 + nums.length - i >= k) {
top--;
}
// 如果栈没有满,当前元素入栈
if (top < k) {
result[top++] = nums[i];
}
}
return result;
}
}
知识点表格总结:
知识点 | 解释 | 在代码中的位置 |
---|---|---|
数组初始化 | 初始化一个定长的数组,并且定义了栈顶指针 | int[] result = new int[k]; 和 int top = 0; |
遍历数组 | 使用 for 循环遍历给定的数组,并对每个元素做处理 |
for (int i = 0; i < nums.length; i++) { ... } |
栈的操作 | 使用一个定长的数组模拟栈,并用 top 指针表示栈顶位置 |
while (top > 0 && result[top - 1] > nums[i] && ... ) { top--; } 和 result[top++] = nums[i]; |
栈顶元素比较 | 当栈顶元素大于当前遍历的元素时,将栈顶元素弹出 | result[top - 1] > nums[i] |
栈的状态判断 | 判断栈是否已满,及栈顶是否大于当前元素 | top < k 和 top > 0 |
字典序判断 | 通过比较和删除元素确保得到的子序列字典序最小 | top - 1 + nums.length - i >= k 确保剩余元素足够构成长度为 k 的子序列 |