统计定界子数组的数目
难度:
标签:
题目描述
代码结果
运行时间: 108 ms, 内存: 26.7 MB
/*
* 思路:
* 使用Java Stream处理定界子数组问题。尽管Stream API不太适合处理双指针问题,但我们仍然可以通过迭代和过滤来实现。
*/
import java.util.stream.IntStream;
public class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
long[] result = {0};
int[] minIndex = {-1};
int[] maxIndex = {-1};
int[] left = {0};
IntStream.range(0, nums.length).forEach(right -> {
if (nums[right] < minK || nums[right] > maxK) {
left[0] = right + 1;
minIndex[0] = -1;
maxIndex[0] = -1;
}
if (nums[right] == minK) minIndex[0] = right;
if (nums[right] == maxK) maxIndex[0] = right;
if (minIndex[0] != -1 && maxIndex[0] != -1) {
result[0] += Math.max(0, Math.min(minIndex[0], maxIndex[0]) - left[0] + 1);
}
});
return result[0];
}
}
解释
方法:
此题解采用滑动窗口的策略,通过一次遍历来统计符合条件的子数组。对于数组中的每一个元素,我们维护两个变量 premin 和 premax 来记录满足条件 minK 和 maxK 的最近的索引位置。当遍历到的元素值小于 minK 或大于 maxK 时,说明当前元素不能被包含在任何有效的子数组中,此时需要重置 premin、premax,并将左指针 l 移动到当前右指针的下一个位置。如果当前元素等于 minK 或 maxK,则更新 premin 或 premax 的值。只有当 premin 和 premax 都被有效更新后,才计算当前的右指针 r 到左指针 l 之间的符合条件的子数组数量,增加的数量为 min(premin, premax) - l + 1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中,为什么滑动窗口的方法适用于这个问题,而不是使用其他算法如动态规划或分治算法?
▷🦆
滑动窗口中,当遇到元素值不在[minK, maxK]范围内时,需要重置premin和premax,这种重置的操作是否会导致一些潜在的子数组被遗漏?
▷🦆
题解中提到当premin和premax都被有效更新后,则计算子数组数量。这种方法是否保证了在所有情况下都能正确计算出定界子数组的数量,特别是在数组元素重复或极端分布的情况下?
▷