题目

题目来源：力扣（LeetCode）

给你一个整数数组 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. 维护一个单调递增的栈，遍历数组，若当前的元素小于栈顶，则弹出栈顶至空或栈顶元素小于当前元素。
  2. n - i： 当前剩下未遍历的元素个数，k - stk.length：栈中仍需要的元素个数，若 n - 1 < k - stk.length， 即当前剩下未遍历的元素个数 小于 栈中需要的元素个数，则全部放进栈里，无须进入while 循环。
  3. 若栈内元素个数多于k个，则弹出至只剩k个。

通过一个示例来加深理解：

看「示例 1」：
输入：nums = [3, 5, 2, 6], k = 2
保留 2 个元素，需要移除 2 个元素。依次读入输入数组到一个线性数据结构：

  • 读到 3，加入 3，此时 [3]；
  • 读到 5，加入 5，此时 [3, 5]；
  • 读到 2，此时 2 比之前的 5 要小，因此可以舍弃 5，这是因为 [3, 2, …] 比 [3, 5, …] 更具竞争力。同样地，2 比之前的 3 要小，因此可以舍弃 3，此时线性数据结构为空，加入 2。5 比 3 后加入线性数据结构，先出，恰好符合「后进先出」的规律，因此使用「栈」。
  • 读到 6，加入 6，此时 [2, 6] 为所求。
  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number[]}
  5.  */
  6. // 维护单调递增栈
  7. var mostCompetitive = function (nums, k) {
  8.   // 单调递增栈，维护子序列的元素，栈中的元素只能有 k 个，并且栈中的元素是单调递增的
  9.   const stack = [];
  10.   const len = nums.length;
  11.   // 从左到右遍历数组，比较当前遍历的元素与栈顶元素的大小
  12.   // 如果当前遍历的元素 小于 栈顶元素，则弹出栈顶至空或栈顶元素小于当前元素，然后当前遍历的元素入栈
  13.   for (let i = 0; i < len; i++) {
  14.     // len - i 数组中当前剩下为遍历的元素个数
  15.     // k - stack.length 栈中还需要的元素个数
  16.     // 如果 (len - i) < (k - stack.length) 即当前所剩元素个数 小于 栈中需要的元素个数，那么应该将所剩元素全部入栈
  17.     // 那么反过来，若当前所剩元素个数 大于 栈中需要的元素个数，并且 当前遍历的元素 小于 栈顶元素，那么栈顶元素出栈
  18.     while (stack.length > 0 && nums[i] < stack[stack.length - 1] && len - i > k - stack.length) {
  19.       stack.pop();
  20.     }
  21.     stack.push(nums[i]);
  22.   }
  23.   // 遍历完数组后，若栈中元素个数大于k个，将则栈中多余元素出栈
  24.   while (stack.length > k) stack.pop();
  25.   return stack;
  26. };