↓Skip to main content
  1. Posts/

LeetCode-3413 收集连续 K 个袋子可以获得的最多硬币数量

·1 min·
Table of Contents

LeetCode-3413 收集连续 K 个袋子可以获得的最多硬币数量 #

Solution 1 #

LeetCode-2271「毯子覆盖的最多白色砖块数」的带权版本, 同样使用滑动窗口来解决. 需要注意的是权重破坏了对称性, 要考虑落在右端点 + 落在左端点的情况.

代码如下:

class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        n = len(coins)
        ans = 0

        def f():
            cover = idx = 0
            for i in range(n):
                cover += (coins[i][1] - coins[i][0] + 1) * coins[i][2]
                while coins[idx][1] <= coins[i][1] - k:
                    cover -= (coins[idx][1] - coins[idx][0] + 1) * coins[idx][2]
                    idx += 1
                uncover = max(0, coins[i][1] - k + 1 - coins[idx][0]) * coins[idx][2]
                nonlocal ans
                ans = max(ans, cover - uncover)

        coins.sort()
        f()

        coins = [(-r, -l, c) for (l, r, c) in coins]
        coins.sort()
        f()

        return ans