2025-07-20：收集连续 K 个袋子可以获得的最多硬币数量。用go语言，在一条数轴上，每个整数坐标对应一个独立的袋子。某些

福大大架构师每日一题

发布于 2025-07-20 09:49:57

1250

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-07-20：收集连续 K 个袋子可以获得的最多硬币数量。用go语言，在一条数轴上，每个整数坐标对应一个独立的袋子。某些袋子中装有硬币。

输入是一个二维数组 coins，其中每个元素 coins[i] = [li, ri, ci] 表示从坐标 li 到 ri（包括两端点）范围内的每个袋子里都放有 ci 枚硬币。已知这些区间彼此不重叠。

再给出一个整数 k，表示你可以从数轴上选择任意连续的 k 个袋子，收集其中的硬币。

请计算并返回选择连续 k 个袋子时，能够获得的硬币最大数量。

1 <= coins.length <= 100000。

1 <= k <= 1000000000。

coins[i] == [li, ri, ci]。

1 <= li <= ri <= 1000000000。

1 <= ci <= 1000。

给定的区间互不重叠。

输入： coins = [[8,10,1],[1,3,2],[5,6,4]], k = 4。

输出： 10。

解释：

选择坐标为 [3, 4, 5, 6] 的袋子可以获得最多硬币：2 + 0 + 4 + 4 = 10。

题目来自力扣3413。

解决步骤

1. 排序区间：
- • 首先将所有区间按照起始坐标 li 从小到大排序。这样可以确保区间是有序的，便于后续处理。
2. 滑动窗口：
- • 使用滑动窗口的思想来遍历所有可能的连续 k 个袋子。滑动窗口的起始和结束位置需要动态调整，以确保窗口始终覆盖 k 个连续的袋子。
- • 初始化两个指针 left 和 right，分别表示当前窗口的起始和结束区间。
- • 初始化 cover 表示当前窗口覆盖的硬币总数。
3. 计算覆盖的硬币：
- • 对于每个区间 [l, r, c]，计算该区间内有多少袋子被当前窗口覆盖。
- • 如果当前区间的结束坐标 r 完全在窗口内，则整个区间的袋子都贡献硬币：(r - l + 1) * c。
- • 如果当前区间只有部分被窗口覆盖，则计算被覆盖的部分：(窗口结束 - l + 1) * c。
- • 如果当前区间完全不在窗口内，则跳过。
4. 调整窗口：
- • 移动窗口时，需要移除左边不再覆盖的区间的硬币贡献。
- • 如果窗口的起始位置超过了某个区间的结束位置，则将该区间的贡献从 cover 中减去，并移动 left 指针。
5. 反向处理：
- • 由于滑动窗口可能从左边或右边覆盖部分区间，因此需要反向处理一次（即从右到左滑动窗口），以确保所有可能的连续 k 个袋子都被考虑到。
6. 最大值更新：
- • 在每次窗口移动后，计算当前窗口覆盖的硬币总数，并更新全局最大值。

时间复杂度

• 排序区间：O(n log n)，其中 n 是区间的数量。
• 滑动窗口：每个区间最多被 left 和 right 指针各访问一次，因此是 O(n)。
• 反向处理：同样是 O(n)。
• 总时间复杂度：O(n log n)（排序主导）。

空间复杂度

• 排序需要 O(log n) 的栈空间（快速排序的递归深度）。
• 其他变量使用常数空间。
• 总空间复杂度：O(log n)。

总结

通过排序和滑动窗口的结合，我们高效地找到了连续 k 个袋子能收集的最大硬币数量。排序确保了区间有序，滑动窗口避免了重复计算，从而在合理的时间内解决问题。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

// 2271. 毯子覆盖的最多白色砖块数
func maximumWhiteTiles(tiles [][]int, carpetLen int) (ans int) {
    cover, left := 0, 0
    for _, tile := range tiles {
        tl, tr, c := tile[0], tile[1], tile[2]
        cover += (tr - tl + 1) * c
        for tiles[left][1]+carpetLen-1 < tr {
            cover -= (tiles[left][1] - tiles[left][0] + 1) * tiles[left][2]
            left++
        }
        uncover := max((tr-carpetLen+1-tiles[left][0])*tiles[left][2], 0)
        ans = max(ans, cover-uncover)
    }
    return
}

func maximumCoins(coins [][]int, k int)int64 {
    slices.SortFunc(coins, func(a, b []int)int { return a[0] - b[0] })
    ans := maximumWhiteTiles(coins, k)

    slices.Reverse(coins)
    for _, t := range coins {
        t[0], t[1] = -t[1], -t[0]
    }
    returnint64(max(ans, maximumWhiteTiles(coins, k)))
}

func main() {
    coins := [][]int{{8,10,1},{1,3,2},{5,6,4}}
    k := 4
    result := maximumCoins(coins,k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def maximumWhiteTiles(tiles: List[List[int]], carpetLen: int) -> int:
    ans = 0
    cover = 0
    left = 0

    for right in range(len(tiles)):
        tl, tr, c = tiles[right]
        cover += (tr - tl + 1) * c

        # 当区间无法被地毯覆盖时，移动左指针缩小覆盖区间
        while tiles[left][1] + carpetLen - 1 < tr:
            cover -= (tiles[left][1] - tiles[left][0] + 1) * tiles[left][2]
            left += 1

        # 计算未覆盖部分的硬币数
        uncover = max((tr - carpetLen + 1 - tiles[left][0]) * tiles[left][2], 0)
        ans = max(ans, cover - uncover)

    return ans

def maximumCoins(coins: List[List[int]], k: int) -> int:
    # 按左端点升序排序
    coins.sort(key=lambda x: x[0])
    ans = maximumWhiteTiles(coins, k)

    # 逆序列表
    coins.reverse()
    # 对区间取负数并交换左右端点位置，转换成类似负轴区间，方便再调用一次
    for t in coins:
        t[0], t[1] = -t[1], -t[0]

    ans = max(ans, maximumWhiteTiles(coins, k))
    return ans

if __name__ == "__main__":
    coins = [[8,10,1],[1,3,2],[5,6,4]]
    k = 4
    result = maximumCoins(coins, k)
    print(result)