统计最大元素出现至少 K 次的子数组
难度:
标签:
题目描述
You are given an integer array nums and a positive integer k.
Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [1,3,2,3,3], k = 2 Output: 6 Explanation: The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
Example 2:
Input: nums = [1,4,2,1], k = 3 Output: 0 Explanation: No subarray contains the element 4 at least 3 times.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1061 <= k <= 105
代码结果
运行时间: 100 ms, 内存: 27.0 MB
/*
* 题目思路：
* 给定一个整数数组 nums 和一个正整数 k，要求统计所有满足 nums 中的最大元素至少出现 k 次的子数组。
* 使用 Java Stream 的方法实现：
* 1. 使用嵌套循环生成所有子数组。
* 2. 对每一个子数组，使用流处理找到最大值及其出现次数。
* 3. 统计满足条件的子数组数量。
*/
import java.util.stream.IntStream;
public class Solution {
public long countSubarrays(int[] nums, int k) {
return IntStream.range(0, nums.length)
.flatMap(i -> IntStream.range(i, nums.length)
.mapToObj(j -> IntStream.rangeClosed(i, j).map(idx -> nums[idx]).toArray())
)
.filter(subarray -> {
int max = IntStream.of(subarray).max().orElse(Integer.MIN_VALUE);
long maxCount = IntStream.of(subarray).filter(x -> x == max).count();
return maxCount >= k;
})
.count();
}
}
解释
方法:
本题解使用了双指针方法来统计满足条件的子数组数量。首先，找到数组中的最大元素t。然后，使用两个指针left和right来遍历数组，right指针向右移动来扩展当前考虑的子数组，left指针向右移动来缩小子数组。当子数组中最大元素t的出现次数达到k时，left指针开始移动，直到t的出现次数再次小于k。这样，对于每个right指针的位置，都可以计算出以right为结束点的、满足条件的子数组数量，即left指针当前的位置数。最后，将所有这些数量累加起来即为答案。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
如何确保双指针策略能够准确统计所有满足条件的子数组，而不会错过任何一个可能的子数组？
▷🦆
在题解中，当最大元素t的计数达到k时，左指针开始移动直到计数再次小于k。这种操作是否可能导致对某些子数组的重复计数？
▷🦆
题解中提到累加左指针的位置数来统计满足条件的子数组数量，这个方法的正确性依据是什么？
▷🦆
当数组中最大值t的出现次数超过k时，如何处理这些额外的出现次数以确保统计的精确性？
▷