Easy

题目描述

给你一个整数数组 nums 和一个整数 k。你需要找到 nums 中长度为 k 且和最大的子序列。

返回任意一个长度为 k 的此类子序列的整数数组。

子序列是一个可以通过删除某些或不删除元素而不改变其余元素顺序，从另一个数组派生的数组。

示例 1：

输入：nums = [2,1,3,3], k = 2
输出：[3,3]
解释：
子序列的最大和为 3 + 3 = 6。

示例 2：

输入：nums = [-1,-2,3,4], k = 3
输出：[-1,3,4]
解释：
子序列的最大和为 -1 + 3 + 4 = 6。

示例 3：

输入：nums = [3,4,3,3], k = 2
输出：[3,4]
解释：
子序列的最大和为 3 + 4 = 7。
另一个可能的子序列是 [4, 3]。

约束条件：

  • 1 <= nums.length <= 1000
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

提示：

  • 从贪心的角度来看，你应该选择哪 k 个元素？
  • 你能在保持索引的同时对数组进行排序吗？

解题思路

解题思路

这道题的核心思想是贪心算法：要获得和最大的子序列，我们应该选择数组中最大的 k 个元素，但同时需要保持它们在原数组中的相对顺序。

主要解法分析：

方法一：排序 + 索引记录（推荐）

  1. 创建索引-值对，记录每个元素的原始位置
  2. 按值从大到小排序，选择前 k 个最大的元素
  3. 按原始索引排序，保持相对顺序
  4. 提取值构成结果

方法二：优先队列 使用最小堆维护当前最大的 k 个元素，遍历数组时动态更新。

方法三：部分排序 使用 nth_element 找到第 k 大的元素作为阈值，然后选择所有大于等于阈值的元素。

复杂度对比：

  • 方法一最直观且易于理解
  • 方法二空间效率更高
  • 方法三在某些情况下时间效率最优

这里采用方法一，因为它思路清晰，代码简洁，且在题目约束下性能完全够用。

代码实现

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        int n = nums.size();
        vector<pair<int, int>> indexed_nums;
        
        // 创建 (值, 索引) 对
        for (int i = 0; i < n; i++) {
            indexed_nums.push_back({nums[i], i});
        }
        
        // 按值降序排序
        sort(indexed_nums.begin(), indexed_nums.end(), greater<pair<int, int>>());
        
        // 选择前 k 个最大值的索引
        vector<int> selected_indices;
        for (int i = 0; i < k; i++) {
            selected_indices.push_back(indexed_nums[i].second);
        }
        
        // 按原始顺序排序索引
        sort(selected_indices.begin(), selected_indices.end());
        
        // 构建结果
        vector<int> result;
        for (int idx : selected_indices) {
            result.push_back(nums[idx]);
        }
        
        return result;
    }
};

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        
        # 创建 (值, 索引) 对
        indexed_nums = [(nums[i], i) for i in range(n)]
        
        # 按值降序排序
        indexed_nums.sort(reverse=True)
        
        # 选择前 k 个最大值的索引
        selected_indices = [indexed_nums[i][1] for i in range(k)]
        
        # 按原始顺序排序索引
        selected_indices.sort()
        
        # 构建结果
        result = [nums[idx] for idx in selected_indices]
        
        return result

public class Solution {
    public int[] MaxSubsequence(int[] nums, int k) {
        int n = nums.Length;
        
        // 创建 (值, 索引) 对
        var indexedNums = new List<(int value, int index)>();
        for (int i = 0; i < n; i++) {
            indexedNums.Add((nums[i], i));
        }
        
        // 按值降序排序
        indexedNums.Sort((a, b) => b.value.CompareTo(a.value));
        
        // 选择前 k 个最大值的索引
        var selectedIndices = new List<int>();
        for (int i = 0; i < k; i++) {
            selectedIndices.Add(indexedNums[i].index);
        }
        
        // 按原始顺序排序索引
        selectedIndices.Sort();
        
        // 构建结果
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = nums[selectedIndices[i]];
        }
        
        return result;
    }
}

var maxSubsequence = function(nums, k) {
    const n = nums.length;
    
    // 创建 [值, 索引] 对
    const indexedNums = nums.map((value, index) => [value, index]);
    
    // 按值降序排序
    indexedNums.sort((a, b) => b[0] - a[0]);
    
    // 选择前 k 个最大值的索引
    const selectedIndices = [];
    for (let i = 0; i < k; i++) {
        selectedIndices.push(indexedNums[i][1]);
    }
    
    // 按原始顺序排序索引
    selectedIndices.sort((a, b) => a - b);
    
    // 构建结果
    const result = [];
    for (const idx of selectedIndices) {
        result.push(nums[idx]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n log n)
空间复杂度O(n)

复杂度说明：

  • 时间复杂度： O(n log n)，主要来自两次排序操作
  • 空间复杂度： O(n)，需要额外空间存储索引-值对和选中的索引

相关题目