leetcode
leetcode 2101 ~ 2150
统计定界子数组的数目

统计定界子数组的数目

难度:

标签:

题目描述

代码结果

运行时间: 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]范围时快速调整。动态规划通常适用于求解最优子结构问题,而这里需要连续跟踪最小和最大索引的更新,分治算法则适用于可以被分解为独立子问题的情况,但本题中子数组的界定高度依赖于全局的元素分布,因此滑动窗口在此更为高效且直接。
🦆
滑动窗口中,当遇到元素值不在[minK, maxK]范围内时,需要重置premin和premax,这种重置的操作是否会导致一些潜在的子数组被遗漏?
不会导致子数组被遗漏。当元素值不在[minK, maxK]范围内时,任何包含该元素的子数组都不能满足题目要求。因此,重置premin和premax是必要的,因为它们记录的是有效子数组的潜在起点。重置操作后,左指针l移至当前元素的下一个位置,这意味着所有之前可能的、但现在已无效的子数组界定被清除,新的搜索从一个清洁的状态开始,确保所有有效的子数组都能被正确统计,而无效的不会被错误地包含。
🦆
题解中提到当premin和premax都被有效更新后,则计算子数组数量。这种方法是否保证了在所有情况下都能正确计算出定界子数组的数量,特别是在数组元素重复或极端分布的情况下?
是的,该方法可以在所有情况下正确计算定界子数组的数量。这是因为只有当premin和premax都有效时(即都已经遇到了至少一次minK和maxK),才开始计算子数组的数量。这种计算方式确保只有包含了至少一个minK和一个maxK的子数组才被计算。此外,通过计算min(premin, premax) - l + 1,确保了即使在元素重复或极端分布的情况下,所有可能的子数组都能被考虑。这种方法准确地反映了从当前左指针到有效的最小/最大值索引之间的所有子数组,无论数组元素如何分布。

相关问题