• Leetcode 3413. Maximum Coins From K Consecutive Bags
  • 1. 解題思路
  • 2. 代碼實(shí)現(xiàn)

• 題目鏈接：3413. Maximum Coins From K Consecutive Bags

1. 解題思路

這一題的話思路上整體上就是一個(gè)遍歷，顯然，要獲得最大的coin，其選取的范圍的必然滿足下述兩種情況之一：

1. 其起始位置剛好位于某個(gè)bag區(qū)間的起始位置；
2. 其終止位置剛好位于某個(gè)bag區(qū)間的終點(diǎn)位置；

因此，我們只需要將所有的bag區(qū)間進(jìn)行排序，依次考察以下每一段區(qū)間作為起始位置和終止位置時(shí)其能夠獲得的coin的數(shù)目，然后從中選出最大值即可。

而給定某一個(gè)區(qū)間作為起始/終止位置之后，我們就可以通過二分查找快速定位到其終止/起始位置所處的區(qū)間，然后通過累積數(shù)組即可快速求得該區(qū)間內(nèi)的所有的coin的數(shù)目。

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(xiàn)如下：

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

提交代碼評(píng)測得到：耗時(shí)855ms，占用內(nèi)存70.6MB。