解决“具有固定边界的计数子数组” | LeetCode 2444 讲解（C++ | JavaScript | Python）

如何解答：“计数具有固定边界的子数组”（LeetCode 2444）

问题评分：困难

主题：数组、滑动窗口、贪婪

各位优秀的开发者们，大家好！

今天，我很高兴能为大家带来一份详细的、适合初学者的指南，来解答一道有趣的题目：
<br/>“计算边界固定的子数组”（LeetCode 2444）。

我会逐步、缓慢、清晰地将其分解，因此，即使您是解决问题的新手，在阅读完这篇文章后，您也会变得更加强大。

问题陈述（简化）

您获得：

• 一个数组nums

• 两个整数：minK和maxK

我们必须计算有多少个连续的子数组同时满足：

• 最小元素恰好是minK

• 最大元素恰好是maxK

重点提醒：子数组是数组的连续切片——不能跳过元素。

️ 循序渐进的思考过程

步骤 1：简单暴力破解（以及失败的原因）

第一个想法：

• 尝试所有可能的子数组。

• 对于每个子数组，检查最小值是否为minK，最大值是否为maxK。

• 如果是的话就算吧。

问题？

• 检查每个子数组 → O(n²)

• 检查每个中的最小值和最大值→O（n）

• 总计： O（n³）——对于大数组来说太慢了。

我们需要一些更智能的东西。

第 2 步：关键观察

扫描阵列时：

1. 如果我们看到一个小于 minK或大于 maxK 的元素，我们就知道：
   

• ❌ 没有有效的子数组可以包含此元素。

• 因此，我们重置了跟踪。

1. 我们必须跟踪：
   

• 我们看到的最新指数等于minK→ ( minPos)

• 我们看到的最新指数等于maxK→ ( maxPos)

1. 在每个位置i，如果minK和maxK均已出现：
   

• 最早的 ( min(minPos, maxPos)) 标记着以 结束的有效子数组的开始i。

1. 但是，如果在最后一个有效的minK或之后出现无效数字maxK，我们必须忽略它。

步骤 3：视觉演练

让我们想象一下：

nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5

• i = 0：nums[0] = 1 → 匹配 minK

• i = 1：nums[1] = 3 → 介于 minK 和 maxK 之间

• i = 2：nums[2] = 5 → 匹配 maxK

现在，从i=0到i=2，我们同时有了 1 和 5 ——一个有效的子数组！

我们还可以有子数组：

• [1,3,5]

• [3,5]（不再从 1 开始，但仍然有效）

因此，在每个索引处，我们可以计算出有多少个有效子数组在那里结束。

步骤 4：代码策略（总结）

• 循环遍历数组。

• 持续更新：

• minPos：最后在哪里minK

• maxPos：最后在哪里maxK

• lastInvalidIndex：元素超出范围的最后一个索引

• 每一步：

• 计算validStart = min(minPos, maxPos)

• 如果是的话，请添加validStart - lastInvalidIndex到答案中。

时间和空间复杂度

✨ 完整的工作解决方案（C++、JavaScript、Python）

C++ 解决方案

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long ans = 0;
        int minPos = -1, maxPos = -1, lastInvalidIndex = -1;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                lastInvalidIndex = i;
            }
            if (nums[i] == minK) {
                minPos = i;
            }
            if (nums[i] == maxK) {
                maxPos = i;
            }

            long long validStart = min(minPos, maxPos);
            long long count = validStart - lastInvalidIndex;
            ans += (count > 0) ? count : 0;
        }

        return ans;
    }
};

JavaScript 解决方案

var countSubarrays = function(nums, minK, maxK) {
    let ans = 0;
    let minPos = -1, maxPos = -1, lastInvalidIndex = -1;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < minK || nums[i] > maxK) {
            lastInvalidIndex = i;
        }
        if (nums[i] === minK) {
            minPos = i;
        }
        if (nums[i] === maxK) {
            maxPos = i;
        }

        let validStart = Math.min(minPos, maxPos);
        let count = validStart - lastInvalidIndex;
        ans += (count > 0) ? count : 0;
    }

    return ans;
};

Python 解决方案

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        ans = 0
        min_pos = -1
        max_pos = -1
        last_invalid_index = -1

        for i, num in enumerate(nums):
            if num < minK or num > maxK:
                last_invalid_index = i
            if num == minK:
                min_pos = i
            if num == maxK:
                max_pos = i

            valid_start = min(min_pos, max_pos)
            count = valid_start - last_invalid_index
            ans += count if count > 0 else 0

        return ans

最后总结

• 当元素超出界限时要小心——立即重置。

• 始终跟踪和的最新发生情况。minKmaxK

• 单次传递解决方案通常隐藏在巧妙的索引跟踪之后。

这个问题教你模式识别、窗口管理和贪婪优化——所有这些对于高级编码面试都至关重要！