这是 LeetCode 2444. Count Subarrays With Fixed Bounds(统计定界子数组的数目)的 JavaScript 实现。

题目理解

求满足以下三个条件的子数组数量:
1. 子数组内的最小值恰好等于 `minK`
2. 子数组内的最大值恰好等于 `maxK`
3. 子数组内的所有元素都在 `[minK, maxK]` 范围内

核心思路:滑动窗口

维护三个关键位置:
- `leftBound`:最近一次遇到非法元素(`< minK` 或 `> maxK`)的位置
- `minPos`:最近一次遇到 `minK` 的位置
- `maxPos`:最近一次遇到 `maxK` 的位置

对于当前位置 `i`,以 `i` 结尾的有效子数组数量为 `max(0, min(minPos, maxPos) - leftBound)`。

JavaScript 代码

```javascript
/**
 * @param {number[]} nums
 * @param {number} minK
 * @param {number} maxK
 * @return {number}
 */
var countSubarrays = function(nums, minK, maxK) {
    let ans = 0;
    
    let leftBound = -1;   // 最近一次非法元素的位置
    let minPos = -1;      // 最近一次 minK 的位置
    let maxPos = -1;      // 最近一次 maxK 的位置
    
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        
        // 遇到非法元素,更新左边界,并重置 minPos 和 maxPos
        if (x < minK || x > maxK) {
            leftBound = i;
            minPos = -1;
            maxPos = -1;
            continue;
        }
        
        if (x === minK) minPos = i;
        if (x === maxK) maxPos = i;
        
        // 必须同时遇到过 minK 和 maxK
        if (minPos !== -1 && maxPos !== -1) {
            // 以 i 结尾的有效子数组,起点可以是 (leftBound, min(minPos, maxPos)] 中的任意位置
            ans += Math.min(minPos, maxPos) - leftBound;
        }
    }
    
    return ans;
};
```

示例验证

输入:`nums = [1,3,5,2,7,5], minK = 1, maxK = 5`

输出:`2`

过程:
- i=0, x=1: minPos=0, maxPos=-1 → 不满足
- i=1, x=3: minPos=0, maxPos=-1 → 不满足
- i=2, x=5: minPos=0, maxPos=2 → ans += min(0,2)-(-1) = 1 → 子数组 `[1,3,5]`
- i=3, x=2: minPos=0, maxPos=2 → ans += 0-(-1) = 1 → 子数组 `[1,3,5,2]`
- i=4, x=7: 非法,leftBound=4, 重置
- i=5, x=5: minPos=-1, maxPos=5 → 不满足(还没遇到 minK)

最终 ans = 2,正确。

复杂度分析

项目    复杂度    
时间    O(n) — 单次遍历    
空间    O(1) — 只使用常数额外空间

 

更多推荐