class Solution {
public:
int beautifulBouquet(vector<int>& flowers, int cnt) {
}
};
LCP 68. 美观的花束
力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 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^51 <= flowers[i] <= 10^51 <= cnt <= 10^5原站题解
python3 解法, 执行用时: 284 ms, 内存消耗: 25.1 MB, 提交时间: 2022-11-18 14:51:48
class Solution:
def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:
ans = left = 0
c = Counter()
for right, x in enumerate(flowers):
c[x] += 1
while c[x] > cnt:
c[flowers[left]] -= 1
left += 1 # 左指针右移1位
ans += right - left + 1
return ans
golang 解法, 执行用时: 96 ms, 内存消耗: 8.9 MB, 提交时间: 2022-11-18 14:43:24
func beautifulBouquet(flowers []int, cnt int) (ans int) {
c := map[int]int{}
left := 0
for right, x := range flowers {
c[x]++
for c[x] > cnt {
c[flowers[left]]--
left++
}
ans += right - left + 1
}
return ans % (1e9 + 7)
}
python3 解法, 执行用时: 288 ms, 内存消耗: 25 MB, 提交时间: 2022-11-18 14:40:43
class Solution:
def beautifulBouquet(self, flowers: List[int], cnt: int) -> int:
ans = left = 0
c = Counter()
for right, x in enumerate(flowers):
c[x] += 1
while c[x] > cnt:
c[flowers[left]] -= 1
left += 1
ans += right - left + 1
return ans % (10 ** 9 + 7)