1403. 非递增顺序的最小子序列

🟢   🔖  贪心 数组 排序  🔗 力扣 LeetCode

题目

Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.

If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.

Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.

Example 1:

Input: nums = [4,3,10,9,8]

Output: [10,9]

Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included. However, the subsequence [10,9] has the maximum total sum of its elements.

Example 2:

Input: nums = [4,4,7,6,7]

Output: [7,7,6]

Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to be returned in non-increasing order.

Constraints:

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 100

题目大意

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。

与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

注意 ，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。

示例 1：

输入： nums = [4,3,10,9,8]

输出：[10,9]

解释： 子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。

示例 2：

输入： nums = [4,4,7,6,7]

输出：[7,7,6]

解释： 子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。

提示：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 100

解题思路

1. 对数组排序
   将数组从大到小排序，这样可以直接从排序后的数组中依次选择最大的元素。

2. 贪心算法
   遍历排序后的数组，累加元素值，直到子序列的和超过剩余部分的和（即子序列和大于总和的一半）。

3. 返回结果
   返回构成子序列的数组部分。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是数组的长度。

  • 排序：数组排序的时间复杂度为 O(n log n)。
  • 遍历：遍历排序后的数组一次，时间复杂度为 O(n)。

• 空间复杂度：O(k)，其中 k 是子序列的长度，结果数组 res 使用额外空间 O(k)，排序操作是原地排序，不需要额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var minSubsequence = function (nums) {
	// 按降序排序
	nums.sort((a, b) => b - a);

	const totalSum = nums.reduce((acc, cur) => acc + cur, 0); // 计算总和
	let subSum = 0; // 子序列和
	const res = []; // 存储子序列

	// 遍历排序后的数组，直到子序列和超过剩余部分
	for (let num of nums) {
		subSum += num;
		res.push(num);
		if (subSum * 2 > totalSum) {
			break;
		}
	}

	return res; // 返回结果
};

相关题目

题号	标题	题解	标签	难度	力扣
2210	统计数组中峰和谷的数量	[✓]	数组	🟢	🀄️ 🔗