Leetcode 3413. Maximum Coins From K Consecutive Bags
- Leetcode 3413. Maximum Coins From K Consecutive Bags
- 1. 解题思路
- 2. 代码实现
- 题目链接：3413. Maximum Coins From K Consecutive Bags
1. 解题思路
这一题的话思路上整体上就是一个遍历，显然，要获得最大的coin，其选取的范围的必然满足下述两种情况之一：
- 其起始位置刚好位于某个bag区间的起始位置；
- 其终止位置刚好位于某个bag区间的终点位置；
因此，我们只需要将所有的bag区间进行排序，依次考察以下每一段区间作为起始位置和终止位置时其能够获得的coin的数目，然后从中选出最大值即可。
而给定某一个区间作为起始/终止位置之后，我们就可以通过二分查找快速定位到其终止/起始位置所处的区间，然后通过累积数组即可快速求得该区间内的所有的coin的数目。
2. 代码实现
给出python代码实现如下：
class Solution:def maximumCoins(self, coins: List[List[int]], k: int) -> int:n = len(coins)coins = sorted(coins)cumsums = [0 for _ in range(n+1)]for i, (l, r, c) in enumerate(coins):cumsums[i+1] = cumsums[i] + (r-l+1) * cans = 0for i, (l, r, c) in enumerate(coins):# start from lj = bisect.bisect_left(coins, [l+k, l+k, 0])if coins[j-1][1] < l+k:ans = max(ans, cumsums[j]-cumsums[i])else:ans = max(ans, cumsums[j-1]-cumsums[i] + (l+k - coins[j-1][0]) * coins[j-1][2])# end by rj = bisect.bisect_left(coins, [r-k+1, r-k+1, 0])if j > i:ans = max(ans, k * coins[i][2])elif j == 0 or coins[j-1][1] <= r-k:ans = max(ans, cumsums[i+1]-cumsums[j])else:ans = max(ans, cumsums[i+1]-cumsums[j] + (coins[j-1][1]-(r-k)) * coins[j-1][2])return ans
提交代码评测得到：耗时855ms，占用内存70.6MB。