当前位置：首页 > web >正文

力扣2444. 统计定界子数组的数目：Java三种解法详解

web 2025/5/6 23:52:58

力扣2444. 统计定界子数组的数目：Java三种解法详解

题目描述

给定整数数组 nums 和两个整数 minK 和 maxK，统计满足以下条件的子数组数目：

子数组的最小值等于 minK；
子数组的最大值等于 maxK。

示例：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：满足条件的子数组为 [1,3,5] 和 [1,3,5,2]。

解法一：单次遍历 + 边界标记（推荐）

代码实现

class Solution {public long countSubarrays(int[] nums, int minK, int maxK) {int n = nums.length;long ans = 0;int minPos = -1, maxPos = -1, border = -1;for (int i = 0; i < n; i++) {// 更新越界标记if (nums[i] < minK || nums[i] > maxK) {border = i;}// 更新最近的最小值和最大值位置if (nums[i] == minK) {minPos = i;}if (nums[i] == maxK) {maxPos = i;}// 计算当前可形成子数组的数量ans += Math.max(0, Math.min(minPos, maxPos) - border);}return ans;}
}

复杂度分析

时间复杂度：O(n)，仅需一次遍历数组。
空间复杂度：O(1)，仅使用常数变量存储标记。

核心思路

标记关键边界：
- border：记录最近出现不满足 minK ≤ num ≤ maxK 的元素位置，作为子数组的左边界限制。
- minPos 和 maxPos：分别记录最近出现的 minK 和 maxK 的位置。
统计逻辑：
- 遍历时，若当前元素是 minK 或 maxK，更新对应位置。
- 有效子数组的左端点范围为 (border, min(minPos, maxPos)]，每次遍历累加有效子数组数量。

解法二：滑动窗口（双指针）

代码实现

class Solution {public long countSubarrays(int[] nums, int minK, int maxK) {int n = nums.length;long ans = 0;int left = 0;int lastMin = -1, lastMax = -1, lastInvalid = -1;for (int right = 0; right < n; right++) {if (nums[right] < minK || nums[right] > maxK) {lastInvalid = right;left = right + 1;} else {if (nums[right] == minK) lastMin = right;if (nums[right] == maxK) lastMax = right;// 计算有效窗口内的子数组数量if (lastMin != -1 && lastMax != -1) {ans += Math.max(0, Math.min(lastMin, lastMax) - lastInvalid);}}}return ans;}
}

复杂度分析

时间复杂度：O(n)，单次遍历数组。
空间复杂度：O(1)，仅需常数变量。

核心思路

滑动窗口维护：
- left 和 right 定义窗口范围。
- 当遇到越界元素时，重置窗口起点。
统计条件：
- 窗口内必须包含至少一个 minK 和 maxK。
- 有效子数组的数量由最近的有效位置决定。

解法三：暴力优化（预处理位置）

代码实现

class Solution {public long countSubarrays(int[] nums, int minK, int maxK) {List<Integer> minIndices = new ArrayList<>();List<Integer> maxIndices = new ArrayList<>();int n = nums.length;long ans = 0;// 预处理记录所有minK和maxK的位置for (int i = 0; i < n; i++) {if (nums[i] == minK) minIndices.add(i);if (nums[i] == maxK) maxIndices.add(i);}// 遍历所有可能的子数组for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {if (nums[j] < minK || nums[j] > maxK) break; // 越界则终止// 检查子数组中是否存在minK和maxKif (contains(minIndices, i, j) && contains(maxIndices, i, j)) {ans++;}}}return ans;}private boolean contains(List<Integer> list, int start, int end) {for (int num : list) {if (num >= start && num <= end) return true;}return false;}
}

复杂度分析

时间复杂度：O(n^2)，最坏情况下需双重循环。
空间复杂度：O(n)，存储预处理的位置列表。

核心思路

预处理优化：
- 提前记录所有 minK 和 maxK 的位置。
暴力枚举优化：
- 遍历所有子数组，若子数组不越界且包含 minK 和 maxK，则计数。

各解法对比

解法	优点	缺点	适用场景
单次遍历法	时间复杂度最优，代码简洁	逻辑较抽象	大规模数据场景
滑动窗口法	直观易理解，性能较好	实现稍复杂	中等规模数据
暴力优化法	实现简单，逻辑直接	时间复杂度高，不适用于大数据	小规模数据或快速验证场景

示例解析

以输入 nums = [1,3,5,2,7,5], minK = 1, maxK = 5 为例：

解法一（单次遍历）：
- 遍历到索引2时，minPos=0, maxPos=2, border=-1 → 贡献子数组数量 0 - (-1) = 1。
- 遍历到索引3时，贡献数量 0 - (-1) = 1 → 累计总数2。
解法二（滑动窗口）：
- 窗口右界到索引2时，窗口包含 1,3,5，满足条件 → 计数1。
- 右界到索引3时，仍满足条件 → 计数+1。