当前位置: 面试刷题>> 最大值在界内的子数组个数 (经典算法题500道)


题目描述补充

题目:最大值在界内的子数组个数

给定一个整数数组 nums 和一个整数 k,我们需要找出所有子数组,这些子数组中的最大值不超过 k,并计算这样的子数组有多少个。

示例 1:

输入: nums = [1, 2, 3, 4, 5], k = 3
输出: 9
解释: 符合条件的子数组有 [1], [1, 2], [1, 2, 3], [2], [2, 3], [3], [1, 2], [2, 3], [3]。

示例 2:

输入: nums = [2, 2, 2], k = 2
输出: 7
解释: 符合条件的子数组有 [2], [2], [2], [2, 2], [2, 2], [2, 2, 2], [2]。

解题思路

为了解决这个问题,我们可以使用双指针(也称为滑动窗口)和单调队列(或单调栈)来优化查找过程。但考虑到代码简洁性和面试时间限制,我们可以采用一种更直观的双指针方法,结合前缀和(或动态规划)来优化计算子数组个数的部分。不过,为了简化,这里我们直接采用双指针遍历所有可能的子数组,并检查每个子数组的最大值是否小于等于 k

PHP 示例代码

function numSubarrayBoundedMax($nums, $k) {
    $count = 0;
    $n = count($nums);
    
    for ($i = 0; $i < $n; $i++) {
        $max = $nums[$i];
        if ($max > $k) continue; // 如果当前元素就大于k,则无需继续检查以它为起点的子数组
        
        for ($j = $i; $j < $n; $j++) {
            $max = max($max, $nums[$j]);
            if ($max <= $k) {
                $count += ($j - $i + 1); // 加上以i为起点,j为终点的所有子数组
            } else {
                break; // 一旦最大值超过k,就跳出内层循环
            }
        }
    }
    
    return $count;
}

// 示例用法
$nums = [1, 2, 3, 4, 5];
$k = 3;
echo numSubarrayBoundedMax($nums, $k); // 输出 9

Python 示例代码

def numSubarrayBoundedMax(nums, k):
    count = 0
    n = len(nums)
    
    for i in range(n):
        max_val = nums[i]
        if max_val > k:
            continue
        
        for j in range(i, n):
            max_val = max(max_val, nums[j])
            if max_val <= k:
                count += (j - i + 1)
            else:
                break
    
    return count

# 示例用法
nums = [1, 2, 3, 4, 5]
k = 3
print(numSubarrayBoundedMax(nums, k))  # 输出 9

JavaScript 示例代码

function numSubarrayBoundedMax(nums, k) {
    let count = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let maxVal = nums[i];
        if (maxVal > k) continue;
        
        for (let j = i; j < n; j++) {
            maxVal = Math.max(maxVal, nums[j]);
            if (maxVal <= k) {
                count += (j - i + 1);
            } else {
                break;
            }
        }
    }
    
    return count;
}

// 示例用法
const nums = [1, 2, 3, 4, 5];
const k = 3;
console.log(numSubarrayBoundedMax(nums, k)); // 输出 9

码小课网站中有更多相关内容分享给大家学习,包括更高效的算法实现、数据结构详解等,欢迎访问码小课网站深入学习。

推荐面试题