[Day 1] Leetcode 1629. Slowest Key

前言

新的一周开始了！想说从今天开始跟着 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++的笔记整理~