前言

新的一週開始了！想說從今天開始跟著 Leetcode 的 September LeetCoding Challenge 2021開始做，結果沒想到今天這題 1629. Slowest Key 是個非常簡單的easy題~
沒關係，easy還是有可以練習的地方，尤其現在在跟C++在培養感情，從一些基礎的用法開始也不錯。

想法

這題要解非常簡單，想要找到最慢的間隔，我們只要O(n)從頭到尾遍歷過去releaseTimes，紀錄目前最大間隔值就ok了；不過答案要的則是對應該位置的key，所以還需要紀錄有最大間隔的位置，或是直接把那個位置的key也一併存下來。
檢視一下目前的條件，我們要找到最大間隔，所以目前的最大間隔是多少是一定要記錄的，才知道接下來有沒有出現更大的情形；另外一個要記錄的則是位置或字母，我們可以選擇紀錄位置或記錄字母；看了題目要求，它說如果有多個擁有一樣的最大間隔，要找最大字母序的，那就紀錄字母吧！因為光記錄位置我們不能知道該位置的字母序有沒有比較大。
統整以上，我們要記錄的是間隔時間+字母，可以用pair<int,char>來存，又兩個都要找最大的，可以直接比大小，什麼參數都不用加！因為會從第0個先比，所以會先比間隔時間，然後再比第二個，剛好是要找字母序大的，讚！
順順寫出來就OK了~

class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        // record the maxima time and character
        pair<int,char>ans(releaseTimes[0],keysPressed[0]);
        for(int i=1;i<releaseTimes.size();++i){
            ans=max(ans,{releaseTimes[i]-releaseTimes[i-1],keysPressed[i]});
        }
        return ans.second;
    }
};

時間複雜度應該是O(n)，就是依照releaseTimes的大小，而空間則是O(1)，我們都只記錄最大的releaseTime差值 + 一個character。

結語

幫自己設立一個比較簡單的開始XD 接下來應該每天會補充一些些C++的筆記整理~