🔗 🟡 1673. Find the Most Competitive Subsequence 1802

tags: `Weekly Contest 217` `貪心(Greedy)` `單調棧(Monotonic Stack)` `字典序(Lexicographical Order)`

題意

給定一個整數陣列 $nums$ 和一個正整數 $k$ ，返回 $nums$ 中大小為 $k$ ，且 字典序(lexicographical order) 最小的子序列。

如果在子序列 $a$ 和 $b$ （長度相同）的第一個不同位置， $a$ 的數字小於 $b$ 的相應數字，則 $a$ 的字典序更小。例如， $[1,3,4] < [1,3,5]$ ，因為它們的第一個不同位置是最後一個數字， $4$ 小於 $5$ 。

思路：貪心(Greedy) + 單調棧(Monotonic Stack)

基於貪心(Greedy) 思路，為求得字典序最小的子序列，我們需使子序列中前面的數字盡可能小，因此可以使用單調棧(Monotonic Stack) ，將數字依序加入 Stack $st$ 中，並在加入時檢查 $st$ 頂端是否有比當前數字更大的數字，若有，則將其移除，直到棧中的數字個數為 $k$ 為止。

在移除 $st$ 頂端的元素時，需注意最後的答案長度是否足夠，而當枚舉到第 $i$ 個數字時，剩餘未枚舉的數字個數為 $n-i$ ，若剩餘的數字不足以使得 Stack 中的數字個數為 $k$ ，即 $len(st) + n - i \leq k$ ，則不應該再移除 $st$ 頂端的元素。

此外，再加入數字時可以檢查 $st$ 中的數字個數是否已經達到 $k$ ，若已達到則不需再加入數字；也可以繼續加入，但最後返回時只取前 $k$ 個數字。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，每個數字都會被枚舉一次，且最多只有各一次的加入和移除操作。
空間複雜度： $O(k)$ ， $st$ 最多只會存放 $k$ 個數字。

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        st = []
        for i, x in enumerate(nums):
            while st and st[-1] > x and len(st) + n - i > k:
                st.pop()
            if len(st) < k:
                st.append(x)
        return st

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && st.back() > nums[i] && st.size() + n - i > k) {
                st.pop_back();
            }
            if (st.size() < k) st.push_back(nums[i]);
        }
        return st;
    }
};