Leetcode 1561. Maximum Number of Coins You Can Get

题目

解法1：heap

这道题的规律是，每次取剩下堆中的最大的两个值和最小的值组成triplet就可以，剩下的只是实现问题。当时自己做的时候是用一个最大堆和一个最小堆实现的，其实这样比较慢

class Solution:def maxCoins(self, piles: List[int]) -> int:min_heap = piles[:]max_heap = [-num for num in piles]heapq.heapify(max_heap)heapq.heapify(min_heap)ans = 0num_coins = 0while num_coins<len(piles):_max = heapq.heappop(max_heap)sec_max = heapq.heappop(max_heap)ans += -sec_max_min = heapq.heappop(min_heap)num_coins += 3return ans

解法2：sort

直接sort之后只需要管数组的后三分之二即可

class Solution:def maxCoins(self, piles: List[int]) -> int:new_piles = sorted(piles)[-len(piles)//3*2:]count = 0right = len(new_piles)-2while right>=0:count += new_piles[right]right -= 2return count

参考：https://leetcode.com/problems/maximum-number-of-coins-you-can-get/discuss/911694/Easy-Python-While-Loop