元素值大于变化阈值的子数组
难度:
标签:
题目描述
代码结果
运行时间: 163 ms, 内存: 29.1 MB
/*
思路:
1. 使用 Java Stream API 来简化遍历和验证的过程。
2. 计算 threshold / k 并过滤出长度为 k 且所有元素都大于该值的子数组。
3. 返回第一个满足条件的子数组的长度。
*/
import java.util.stream.IntStream;
public class Solution {
public int findSubarrayLength(int[] nums, int threshold) {
return IntStream.rangeClosed(1, nums.length)
.filter(k -> IntStream.range(0, nums.length - k + 1)
.anyMatch(i -> IntStream.range(i, i + k)
.allMatch(j -> nums[j] > (double) threshold / k)))
.findFirst()
.orElse(-1);
}
}
解释
方法:
这个题解首先利用单调栈来预处理出每个元素左右两侧第一个小于它的元素的位置。这样做的目的是为了快速找出以当前元素为最小值的最大可能子数组的长度。然后,该解法遍历整个数组,对于每个元素,计算如果以该元素为最小值时,能形成的最大子数组的长度k,然后检查该元素是否满足条件 num > threshold / k。如果满足,即返回k作为结果。如果遍历完数组都没有找到符合条件的子数组,最终返回-1。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中使用单调栈的目的是什么?为什么单调栈能够有效预处理出每个元素左右两侧第一个小于它的元素的位置?
▷🦆
题解中提到的单调栈在遇到比栈顶元素小的值时就会弹栈,这种操作的复杂度是怎样的?是否能保证整体的时间复杂度在可接受的范围内?
▷🦆
题解中计算子数组长度`k = r - l - 1`的合理性在哪里?为什么要从减去l再减去1?
▷