Description
給定一個 int 陣列以及一個正整數 k，回傳一個長度為 k 的 the most competitive subsequence (注意：此 subsequence 不一定要連續)。當第一個相異的數值出現在陣列一和陣列二時，擁有較小數值的陣列較 competitive，舉列來說 [1, 3, 4] 較 [1, 3, 5] competitive，因為 4 小於 5。
Example 1:
Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.Example 2:
Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]Solution
假設 ans 為將要回傳之變數，我們需要做的事情是，遍歷 nums 的元素，並且將合適的元素推入 ans 當中，而 ans 裡不合適的元素要刪除，最終得到一個長度為 k 的陣列。我們將以以下原則遍歷 nums：
- 當
ans存儲的元素長度小於k時，無條件將遍歷之元素推入ans。但是推入元素前，我們會先進行以下原則的檢查 - 當遍歷到
nums[i]時發現：
$\text{nums[i]} \geq \text{ans[j]}, \text{for } j \in [0, t]$
$\text{nums[i]} < \text{ans[j]}, \text{for } j \in [t + 1, k)$ 則應該將ans[t + 1], ..., a[k - 1]的值全部排除後，再將nums[i]加入ans。
- 必須確保尚未遍歷的元素數量大於
ans的空位，若剩餘的元素剛好等於空位數，則將不再進行原則 2 將元素排除的動作
對於原則1很好理解，因為我們必須確保 ans 有足夠的長度 k，因此當 ans 長度小於 k 時，必須直接將新的遍歷元素加入 ans 中。舉例來說：nums = [100, 100, 100, 100], k = 4，無論 nums[i]的值有多大，我們都必須放入 ans 當中，因為唯有如此才能確保 ans 有足夠的長度(長度為 4)，因此在此例中，我們需要推入所有 nums 的元素至 ans，得到 ans = [100, 100, 100, 100]。
至於原則2，我們想要確保越小的值排在 ans 越前面的位置，假設 k = 4 ，並且在我們遍歷 nums 一段時間後得到 ans = [1, 3, 4, 5]，若下一個遍歷元素為 2，則我們要將 [3, 4, 5] 全部移除再將 2 推入，得到 ans = [1, 2] ，需要將 [3, 4, 5] 排除是因為就算接下來只剩下很大的元素未遍歷而放入 ans 當中，如：ans = [1, 2, 100, 100]，還是會比 ans = [1, 3, 4, 5] 還要 competitive。
最後原則3，我們要確保剩下還未遍歷的值足夠填滿 ans，否則我們將不會在將 ans 的尾部元素刪除，因為若我們刪除 ans 中的任一元素，其長度將永遠達不到 k，違反題目要求。我們以以下幾個例子闡述整個算法。
完整算法如下(in C++)
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> ans;
for (int idx = 0; idx < nums.size(); ++idx)
{
while (ans.size() > 0 &&
nums[idx] < ans.back() &&
k - ans.size() < nums.size() - idx)
{
ans.pop_back();
}
if (ans.size() < k) ans.push_back(nums[idx]);
}
return ans;
}
};