美观的花束

标签: 数组 滑动窗口

难度: Medium

力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 `flowers` 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。 在你选择的插花中，如果每一品种的鲜花数量都不超过 `cnt` 朵，那么我们认为这束插花是 「美观的」。 > - 例如：`[5,5,5,6,6]` 中品种为 `5` 的花有 `3` 朵， 品种为 `6` 的花有 `2` 朵，**每一品种** 的数量均不超过 `3` 请返回在这一排鲜花中，共有多少种可选择的区间，使得插花是「美观的」。 **注意：** - 答案需要以 `1e9 + 7 (1000000007)` 为底取模，如：计算初始结果为：`1000000008`，请返回 `1` **示例 1：** >输入：`flowers = [1,2,3,2], cnt = 1` > >输出：`8` > >解释：相同的鲜花不超过 `1` 朵，共有 `8` 种花束是美观的； >长度为 `1` 的区间 `[1]、[2]、[3]、[2]` 均满足条件，共 `4` 种可选择区间 >长度为 `2` 的区间 `[1,2]、[2,3]、[3,2]` 均满足条件，共 `3` 种可选择区间 >长度为 `3` 的区间 `[1,2,3]` 满足条件，共 `1` 种可选择区间。 >区间 `[2,3,2],[1,2,3,2]` 都包含了 `2` 朵鲜花 `2` ，不满足条件。 >返回总数 `4+3+1 = 8` **示例 2：** >输入：`flowers = [5,3,3,3], cnt = 2` > >输出：`8` **提示：** - `1 <= flowers.length <= 10^5` - `1 <= flowers[i] <= 10^5` - `1 <= cnt <= 10^5`

Submission

运行时间: 144 ms

内存: 26.9 MB

class Solution:
    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:
        MOD = 10 ** 9 + 7
        l, ans = -1, 0
        dic = defaultdict(int)
        for i, x in enumerate(flowers):
            dic[x] += 1
            while dic[x] > cnt:
                l += 1
                dic[flowers[l]] -= 1
            ans += i - l
            ans %= MOD
        return ans

Explain

这个题解使用了滑动窗口（双指针）的方法来寻找所有满足条件的连续子数组（美观的花束）。维护两个指针i和l，其中i是当前考察的花的位置，而l是使得从l到i的子数组满足每种花的数量都不超过cnt的最小可能的起点。使用一个哈希表dic来记录窗口中每种花的数量。遍历flowers数组，对于每个花品种x，增加dic[x]的计数。如果dic[x]超过了cnt，说明当前窗口从l到i不再美观，因此需要将l右移直到dic[x]不超过cnt。每次右移l后，相应地减少dic[flowers[l]]的计数。每个有效的l到i的窗口都是一个美观的花束，i - l表示以i为结束位置的美观花束的数量。结果ans累加这些花束的数量，并且使用MOD来防止溢出。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:
        MOD = 10 ** 9 + 7  # 防止结果溢出的模数
        l, ans = -1, 0  # 初始化左指针l和答案ans
        dic = defaultdict(int)  # 记录窗口中每种花的数量
        for i, x in enumerate(flowers):  # 遍历每朵花
            dic[x] += 1  # 增加当前花品种x的计数
            while dic[x] > cnt:  # 当当前品种数量超过限制时，移动左指针
                l += 1
                dic[flowers[l]] -= 1  # 更新左指针指向花的计数
            ans += i - l  # 计算当前位置结尾的所有美观花束数，并累加到结果中
            ans %= MOD  # 取模保证不溢出
        return ans  # 返回结果

Explore

在双指针方法中，左指针`l`初始设为`-1`是为了逻辑上方便处理子数组的开始边界。当`l`从`-1`开始，`i - l`的结果直接表示从`l + 1`到`i`的区间长度，即当前有效窗口的大小。如果从`0`开始，则在进行第一次计算时会需要特殊处理，以确保区间长度计算正确。使用`-1`作为起始点，简化了代码逻辑，使得每次增加`i`时，直接使用`i - l`能够正确反映新的窗口长度。

当`dic[x] > cnt`时，说明当前花品种`x`的数量已经超过了允许的最大值`cnt`。移动左指针`l`一次是为了逐步减少包含过多`x`的花品种的窗口范围。每次只移动一次是因为我们需要从当前不满足条件的最小窗口开始逐步检查，通过逐个剔除左边界的花，直到窗口中的该花品种数量不超过`cnt`。这种方法确保了每个可能的子数组都被逐一考察，从而不遗漏任何一个美观花束的计算。

在这个算法中，`dic`哈希表确实记录了窗口中每种花的数量，但是这里不存在重复计数的问题。因为算法的目的是计算所有可能的`美观的花束`，即每次窗口调整（无论是扩大还是缩小）都是为了寻找新的有效的花束配置。每次当`i`增加时，计算的是以`i`为结束点的所有有效花束数，这些花束是基于当前窗口状态的合法配置。每次左指针`l`移动时，之前可能的重叠计数已经在之前的迭代中被处理过，当前计数只关注新的有效区间，因此不会有重复计数的问题。