題解 | 「力扣」第 1673 題：找出最具競爭力的子序列（棧）
給你一個整數(shù)數(shù)組 nums 和一個正整數(shù) k ，返回長度為 k 且最具 競爭力 的 nums 子序列。
數(shù)組的子序列是從數(shù)組中刪除一些元素（可能不刪除元素）得到的序列。
在子序列 a 和子序列 b 第一個不相同的位置上，如果 a 中的數(shù)字小于 b 中對應(yīng)的數(shù)字，那么我們稱子序列 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^50 <= nums[i] <= 10^91 <= k <= nums.length
理解題意：
- 子序列的定義：數(shù)組的子序列是從數(shù)組中刪除一些元素（可能不刪除元素）得到的序列。注意：「子序列」的定義要求這些元素保持在原數(shù)組中的相對位置；
- 題目中「最小競爭力」的定義類似于「字典序最小」。如果做過 316. 去除重復(fù)字母 、 402. 移掉 K 位數(shù)字 和 456. 132 模式 就會知道這道問題可能需要用到「?！埂Ｒ虼宋覀冃枰衷S為什么解決這道問題可以用「?！?。
為什么想到用「棧」
看「示例 1」
輸入：nums = [3, 5, 2, 6], k = 2
保留 2 個元素，需要移除 2 個元素。依次讀入輸入數(shù)組到一個線性數(shù)據(jù)結(jié)構(gòu)：
- 讀到 3，加入 3，此時
[3]； - 讀到 5，加入 5，此時
[3, 5]； - 讀到 2，此時 2 比之前的 5 要小，因此可以舍棄 5，這是因為
[3, 2, ...]比[3, 5, ...]更具競爭力。同樣地，2 比之前的 3 要小，因此可以舍棄 3，此時線性數(shù)據(jù)結(jié)構(gòu)為空，加入 2。5 比 3 后加入線性數(shù)據(jù)結(jié)構(gòu)，先出，恰好符合「后進先出」的規(guī)律，因此使用「?！?。 - 讀到 6，加入 6，此時
[2, 6]為所求。
需要注意的地方：
- 根據(jù)數(shù)組的長度和
k計算可以移除的元素的個數(shù)，需要移除的時候才可以移除； - 如果遍歷完成以后還有可以刪除的元素，應(yīng)該從棧的末尾刪除元素。這是因為「?！怪械脑厍『梅蠁握{(diào)不減的特點，從末尾刪除元素可以保證最具競爭力。
參考代碼 1：
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public int[] mostCompetitive(int[] nums, int k) {
int len = nums.length;
if (k == len) {
return nums;
}
// 需要移除的元素的個數(shù)
int removeCount = len - k;
Deque<Integer> stack = new ArrayDeque<>();
for (int num : nums) {
// 注意：只有在有元素可以移除的時候才可以移除
while (removeCount > 0 && !stack.isEmpty() && num < stack.peekLast()) {
stack.removeLast();
removeCount--;
}
stack.addLast(num);
}
// 如果還有可以刪除的元素，從末尾刪除
for (int i = 0; i < removeCount; i++) {
stack.removeLast();
}
// 此時棧中的元素就是最具競爭力的數(shù)組，遍歷棧賦值到數(shù)組上即可
int[] res = new int[k];
int index = k - 1;
for (int i = 0; i < k; i++) {
res[index] = stack.removeLast();
index--;
}
return res;
}
}
說明：這里用 ArrayDeque 是 Java 的文檔 Stack 類里推薦的，使用帶 Last 后綴的 API 是因為 Array 實現(xiàn)操作末尾復(fù)雜度為 ，而
Deque 實現(xiàn)是循環(huán)數(shù)組，其實操作頭尾都可以。只要當作棧來用，API 不必和我一樣。
復(fù)雜度分析：
- 時間復(fù)雜度：
，這里
是輸入數(shù)組的大小，所有元素進棧一次、出棧一次；
- 空間復(fù)雜度：
這一類問題通常而言都可以在棧里先放入一個永遠不可能被移除的元素，這樣在循環(huán)的時候可以省去判斷棧是否為空。根據(jù)題目給出的數(shù)據(jù)范圍，這里放入小于等于 0 的整數(shù)就可以。
參考代碼 2：
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public int[] mostCompetitive(int[] nums, int k) {
int len = nums.length;
if (k == len) {
return nums;
}
int removeCount = len - k;
Deque<Integer> stack = new ArrayDeque<>();
// 哨兵
stack.addLast(0);
for (int num : nums) {
// 因為有 0 的存在，棧一定非空，所以無需判斷棧為空
while (removeCount > 0 && num < stack.peekLast()) {
stack.removeLast();
removeCount--;
}
stack.addLast(num);
}
for (int i = 0; i < removeCount; i++) {
stack.removeLast();
}
int[] res = new int[k];
int index = k - 1;
for (int i = 0; i < k; i++) {
res[index] = stack.removeLast();
index--;
}
return res;
}
}
復(fù)雜度分析：(同「參考代碼 1」)。
總結(jié)
子序列保持元素相對順序，以及「最具競爭力」的定義決定了，解決這道問題恰好符合了「后進先出」的規(guī)律，因此可以使用「棧」，棧內(nèi)的元素恰好保持了單調(diào)不減的特點。
最近正在 B 站講解《算法不好玩》系列教程，地址，以新手視角講解算法與數(shù)據(jù)結(jié)構(gòu)，通俗易懂且不失嚴謹。公眾號：算法不好玩。感謝大家支持！
