当前位置： 面试刷题>> 最大值在界内的子数组个数 (经典算法题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 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课网站中有更多相关内容分享给大家学习**，包括更高效的算法实现、数据结构详解等，欢迎访问码小课网站深入学习。