Hard

题目描述

给你一个整数数组 nums 和两个整数 minK 和 maxK。

nums 的固定边界子数组是满足下述条件的子数组：

  • 子数组中的最小值等于 minK
  • 子数组中的最大值等于 maxK

返回固定边界子数组的数目。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：固定边界子数组是 [1,3,5] 和 [1,3,5,2]。

示例 2：

输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是固定边界子数组。总共有 10 个可能的子数组。

约束条件：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i], minK, maxK <= 10^6

解题思路

这道题的关键思路是使用滑动窗口技术。我们需要找到同时包含 minK 和 maxK 作为最值的子数组。

核心观察：

  1. 首先，任何包含小于 minK 或大于 maxK 的元素的子数组都不可能是有效的
  2. 我们需要将数组分割成若干段，每段内的所有元素都在 [minK, maxK] 范围内
  3. 对于每个有效段，计算其中满足条件的子数组数量

算法步骤：

  1. 使用三个指针：left（当前有效段的起始位置）、minPos（最近一个 minK 的位置）、maxPos（最近一个 maxK 的位置）
  2. 遍历数组，当遇到超出范围的元素时，重置 left 指针
  3. 更新 minPos 和 maxPos，当两者都有效时，以当前位置为右端点的有效子数组数量等于 min(minPos, maxPos) - left + 1

这种方法的优势是只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long result = 0;
        int left = 0;
        int minPos = -1, maxPos = -1;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                left = i + 1;
                minPos = maxPos = -1;
            } else {
                if (nums[i] == minK) minPos = i;
                if (nums[i] == maxK) maxPos = i;
                
                if (minPos != -1 && maxPos != -1) {
                    result += min(minPos, maxPos) - left + 1;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        result = 0
        left = 0
        min_pos = max_pos = -1
        
        for i, num in enumerate(nums):
            if num < minK or num > maxK:
                left = i + 1
                min_pos = max_pos = -1
            else:
                if num == minK:
                    min_pos = i
                if num == maxK:
                    max_pos = i
                
                if min_pos != -1 and max_pos != -1:
                    result += min(min_pos, max_pos) - left + 1
        
        return result

public class Solution {
    public long CountSubarrays(int[] nums, int minK, int maxK) {
        long result = 0;
        int left = 0;
        int minPos = -1, maxPos = -1;
        
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                left = i + 1;
                minPos = maxPos = -1;
            } else {
                if (nums[i] == minK) minPos = i;
                if (nums[i] == maxK) maxPos = i;
                
                if (minPos != -1 && maxPos != -1) {
                    result += Math.Min(minPos, maxPos) - left + 1;
                }
            }
        }
        
        return result;
    }
}

var countSubarrays = function(nums, minK, maxK) {
    let count = 0;
    let minPos = -1, maxPos = -1, leftBound = -1;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < minK || nums[i] > maxK) {
            leftBound = i;
        }
        
        if (nums[i] === minK) {
            minPos = i;
        }
        
        if (nums[i] === maxK) {
            maxPos = i;
        }
        
        count += Math.max(0, Math.min(minPos, maxPos) - leftBound);
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要一次遍历数组
空间复杂度O(1)只使用了常数个额外变量

相关题目