Kimi LeetCode 2444.统计定界子数组的数目 JavaScript实现
这是 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) — 只使用常数额外空间
更多推荐


所有评论(0)