剛學完資料結構
想說為了寒假不要那麼無聊
每天來一題LeetCode直到過年
希望不要太有壓力 又能學到東西

於是第一天開始找適合的題目啦！
看著LeetCode的首頁想了一想


看著下圖第三個欄位
什麼! LeetCode for 新手
像我這種程式小白當然是最適合我的啦！
結果大概30分鐘後發現...


ㄟ不是 才沒幾分鐘就秒殺是怎樣
(雖然有些C++語法忘了還去問Chat大大

挑到太簡單的問題 只好換一個對手
然後就隨便找了一題medium
也就是標題的那個題目：


這題我的思路是
首先抓出陣列中0到s-k(s是陣列元素個數)最小的數字
紀錄該數字的位置l 並把k+1後
再抓出陣列中l+1到k最小的數字
一直重複這個循環直到k==0為止
以下是我的程式碼：

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& arr, int k) {
        int l = -1, temp;
        vector<int> ans;
        while(k > 0){
            temp = 1000000001;
            int s = arr.size();
            for(int i = l + 1; i <= s - k; i++){
                if(arr[i] < temp){
                    temp = arr[i];
                    l = i;
                }
            }
            k--;
            ans.push_back(temp);
        }
        return ans;
    };
};

(當然 這個code也是我一番辛苦是錯才得到的
結果summit後出現這個畫面：


...誒不是 沒事在測資放那麼多0幹嘛啦
一上來就感受到LeetCode滿滿的惡意(X
看起來是時間複雜度要小於O(n)才能通過TLE的限制呢

看看別人的參考code 發現用stack可以有效解決
參考了stack的函式方法 於是寫了下面的code：

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& arr, int k) {
        int l = -1, temp;
        stack<int> st;
        st.push(1000000001);
        for(int i = 0; i < arr.size(); i++){
            while(!st.empty() && arr[i] < st.top() && k - st.size() < arr.size() - i){
                st.pop();
            }
            if(st.size() < k){
                st.push(arr[i]);
            }
        }
        vector<int> ans;
        while(!st.empty()){
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    };
};

然後就成功AC了，好耶！