Medium

题目描述

给你一个整数数组 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 <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

提示：

  • 按字典序，左边的元素比右边的元素具有更高的优先级。你能想到一种从左到右递增构建答案的策略吗？

解题思路

这道题的关键是理解"最具竞争力"的含义：在第一个不同的位置上，数值更小的子序列更具竞争力。这提示我们要贪心地选择尽可能小的数字，且位置要尽可能靠前。

核心思路： 使用单调栈（递增栈）的思想。我们从左到右遍历数组，维护一个结果数组（栈）：

  1. 如果当前元素比栈顶元素小，且还有足够的剩余元素可以选择，就弹出栈顶元素
  2. 将当前元素加入栈中
  3. 最终栈中前k个元素就是答案

关键点：

  • 判断是否可以弹出栈顶：需要保证弹出后，剩余的元素数量仍然足够构成长度为k的子序列
  • 弹出条件：stack.size() + (n - i) > k，即当前栈大小加上剩余元素数量大于k

这种贪心策略保证了我们总是优先选择更小的数字，同时保持字典序最小。

时间复杂度分析： 每个元素最多被压入和弹出栈一次，所以时间复杂度是O(n)。

代码实现

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> stack;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            // 如果当前元素更小，且弹出后仍有足够元素选择，则弹出栈顶
            while (!stack.empty() && stack.back() > nums[i] && 
                   stack.size() + (n - i) > k) {
                stack.pop_back();
            }
            // 如果栈未满，添加当前元素
            if (stack.size() < k) {
                stack.push_back(nums[i]);
            }
        }
        
        return stack;
    }
};

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = []
        n = len(nums)
        
        for i in range(n):
            # 如果当前元素更小，且弹出后仍有足够元素选择，则弹出栈顶
            while stack and stack[-1] > nums[i] and len(stack) + (n - i) > k:
                stack.pop()
            # 如果栈未满，添加当前元素
            if len(stack) < k:
                stack.append(nums[i])
        
        return stack

public class Solution {
    public int[] MostCompetitive(int[] nums, int k) {
        List<int> stack = new List<int>();
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            // 如果当前元素更小，且弹出后仍有足够元素选择，则弹出栈顶
            while (stack.Count > 0 && stack[stack.Count - 1] > nums[i] && 
                   stack.Count + (n - i) > k) {
                stack.RemoveAt(stack.Count - 1);
            }
            // 如果栈未满，添加当前元素
            if (stack.Count < k) {
                stack.Add(nums[i]);
            }
        }
        
        return stack.ToArray();
    }
}

var mostCompetitive = function(nums, k) {
    const stack = [];
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        // 如果当前元素更小，且弹出后仍有足够元素选择，则弹出栈顶
        while (stack.length > 0 && stack[stack.length - 1] > nums[i] && 
               stack.length + (n - i) > k) {
            stack.pop();
        }
        // 如果栈未满，添加当前元素
        if (stack.length < k) {
            stack.push(nums[i]);
        }
    }
    
    return stack;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被压入和弹出栈一次
空间复杂度O(k)栈的大小最多为k

相关题目