LeetCode 解題紀錄 1561. Maximum Number of Coins You Can Get

Maximum Number of Coins You Can Get - LeetCode

題目

總共有 3n 堆的硬幣，一次選出三堆，不能拿最多的那一堆，只能拿中間的，拿完之後可以拿到最多的硬幣數。

限制

• 硬幣堆數介於 3~100000堆，一定是 3 的倍數
• 每一堆硬幣介於 1~10000

觀察

• 每次能拿到最多的硬幣，是目前最多的那一堆的次一堆，而第三堆是多少可以不用在意，因為只需回傳我們可以拿到最多的數目

思路

• 經過排序之後，我們可以持續拿第二大的數目當作為我們可以拿的硬幣數
• 拿完全部 2/3 後，就可以確定已經拿完可以拿的硬幣了
• 剩下的 1/3 ，一定小於或等於拿走的硬幣數，不管它們怎麼搭配應外兩個硬幣堆數，都不會影響結果

Trail 1

https://gist.github.com/kevinchung0921/dec99aafc22d09e91efde045f2fcd1d1

結果

時間複雜度是 O(n log n + n) = O(n log n)，空間複雜度是 O(1)，結果在排行裡不算突出，看了執行速度最快的寫法，原來是使用 count sort，因為只要 size 10001 的陣列就可以讓排序時間降為 O(n)，在單純數字排序時，如果數值不大的時候，可以利用空間來換取一些時間，算是種有趣的作法