LCP 68. 美观的花束

LCP 68. 美观的花束

力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 flowers 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。 在你选择的插花中，如果每一品种的鲜花数量都不超过 cnt 朵，那么我们认为这束插花是 「美观的」。

• 例如：[5,5,5,6,6] 中品种为 5 的花有 3 朵， 品种为 6 的花有 2 朵，每一品种 的数量均不超过 3

请返回在这一排鲜花中，共有多少种可选择的区间，使得插花是「美观的」。

注意：

• 答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1

---

简单来说，就是一个区间内一个数字出现的次数不能超过 k，所以直接上滑动窗口！

为什么这里是 r - l + 1 ？可以想象一下，我们此时把 r 当作不变量，对于每个 l 都一定会被计算，此时我们想象以下，这个给定的 l 对应的 r ，此时对于 给定的 l 对应的右边界为 x（l < x < r）不存在，所以我们需要保证加上所有的对于给定的 l 符合条件的有边界：

func beautifulBouquet(flowers []int, cnt int) int {
    mp := make(map[int]int)
    ans := 0
    l := 0
    for r, x := range flowers {
        mp[x] ++
        for mp[x] > cnt {
            mp[flowers[l]] --
            l ++
        }
        ans += r - l + 1
    }
    return ans % 1000000007
}