主題
題目連結(jié)：
題目意譯：
給定一個整數(shù)陣列 nums 和一正整數(shù) k ，回傳 nums 中大小為 k 之最有競爭力的子序列。
一個陣列的子序列為一個序列其藉由抹除掉一些（也可能沒有）陣列中的元素而得到。
我們定義一序列 a 比一序列 b（長度相同）更有競爭力，如果在 a 、 b 第一個不同之處，序列 a 有著比序列 b 於相同位置之?dāng)?shù)字小的值。例如 [1, 3, 4] 比 [1, 3, 5] 更有競爭力，因為兩者第一個不同的位置為它們的結(jié)尾，而 4 小於 5 。
限制：
1 ≦ nums.length ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 9
1 ≦ k ≦ nums.length
範(fàn)例測資：
範(fàn)例 1：
輸入： nums = [3,5,2,6], k = 2
輸出： [2,6]
解釋： 在所有可能的序列之集合中：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}，[2,6] 最具有競爭力。
範(fàn)例 2：
輸入： nums = [2,4,3,3,5,4,9,6], k = 4
輸出： [2,3,3,4]
解題思維：
經(jīng)過一些觀察，可以看到長度為 k 的最有競爭力之序列 S，其滿足
S[0] 為 nums[0] ～ nums[nums.length - k] 中的最小值；
S[1] 為 nums[S[0] 的取值位置 + 1] ～ nums[nums.length - k + 1] 中的最小值；
S[2] 為 nums[S[1] 的取值位置 + 1] ～ nums[nums.length - k + 2] 中的最小值；
……以此類推。
而我們可以利用一個雙端佇列 Q（Double-Ended Queue，簡稱為 deque）來儲存 nums 中的數(shù)字，期間我們需要維護(hù)使得 Q 中每個元素小於等於其下一個元素。
因此 Q.front() （Q 的左側(cè)/前端）將會是整個佇列裡數(shù)字最小的；而 Q.back()（Q 的右側(cè)/尾端）則是最大值。
因此我們先將 nums[0] ～ nums[nums.length - k - 1] 這 nums.length - k 個數(shù)字放進(jìn) Q 之中。對於每個數(shù)字 nums[i]，先檢查 Q 是不是非空且 Q.back() 是否 > nums[i]。如果成立則代表 Q.back() 在往後已經(jīng)派不上用場了，因此可以被 nums[i] 替換掉，所以將 Q.back() 移除掉。重複此步驟直到條件之一不符合為止。
接著我們才把 nums[i] 放到 Q 的尾端。
然後再掃過剩下的數(shù)字（nums[nums.length - k] ～ 結(jié)尾）。對於數(shù)字 nums[i] 也是按照以上的步驟執(zhí)行。不過這次我們開始要找出 S[0] 、 S[1] 等等之值了。
因此當(dāng)我們執(zhí)行到位置 i = nums.length - k + j （0 ≦ j < k）時，S[j] 之值即為 Q.front()。而因為此時 Q.front() 已經(jīng)被 S[j] 佔有了，所以我們需要將 Q.front() 移除。
掃完之後我們便可以得到一序列 S[0] 、 S[1] 、 …… 、 S[k - 1] ，而這即是 nums 中競爭力最強(qiáng)的子序列（因為我們對於每個位置都盡量去挑最小的值，使競爭力盡可能地強(qiáng)）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
