題目

539. Minimum Time Difference
難度: 中等偏易

題意

給定一字串陣列timePoints，每個字串為HH:MM格式的24小時制時間。
求任兩對時間差之最小值(時間差可以跨過午夜，以分鐘數回傳)

思路

題目要求回傳值以分鐘計算，因此先將字串轉換成整數，HH * 60 + MM。

將分鐘時間點排序好，兩兩相鄰的時間差取最小的。
排序過的時間點，相鄰為1的差距必不大於相鄰為2的差距，因此排序好只需搜尋兩兩相鄰的差即可。
要注意尾到頭(跨夜)的差也要列入計算。

實作

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> minutes;
        for(auto str : timePoints)
        {
            int curr = ((str[0] - '0') * 10 + (str[1] - '0')) * 60 + ((str[3] - '0') * 10 + (str[4] - '0'));
            minutes.push_back(curr);
        }
        sort(minutes.begin(), minutes.end());
        
        int n = minutes.size();
        int res = 24 * 60 - (minutes.back() - minutes.front());
        for(int i = 1; i < n; i++)
            res = min(res, minutes[i] - minutes[i - 1]);
    return res;
    }
};

分析

若時間點的數量為N
時間複雜度: O(NlogN)，排序
空間複雜度: O(N)，儲存時間點

結果

小記

連續兩天用手機刷題，眼睛快瞎了
手機版鐵人發文還有bug，會自己跳轉畫面，最後切電腦版網頁才成功發文