leetcode
leetcode 2001 ~ 2050
元素值大于变化阈值的子数组

元素值大于变化阈值的子数组

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在题解中使用单调栈的目的是什么?为什么单调栈能够有效预处理出每个元素左右两侧第一个小于它的元素的位置?
题解中使用单调栈的目的是为了快速确定每个元素左右两边第一个小于它的元素的位置。这种信息对于确定以当前元素为最小值的最大可能子数组的长度是非常有用的。单调栈通过维护一个元素索引的栈,确保栈内的元素值是单调递减的,使得当遍历到新的元素时,可以快速找到栈顶元素为最近的、且比当前元素小的元素。如果新元素小于栈顶元素,就弹出栈顶,这样可以保持栈的单调性。这种结构使得每个元素被压入和弹出栈的操作最多各发生一次,从而高效地预处理出所需的位置信息。
🦆
题解中提到的单调栈在遇到比栈顶元素小的值时就会弹栈,这种操作的复杂度是怎样的?是否能保证整体的时间复杂度在可接受的范围内?
单调栈的操作复杂度是非常高效的。每个元素最多被压入和弹出栈一次,因此遍历整个数组的过程中,每个元素的进栈和出栈操作的总次数是常数,即O(1)。因此,对于整个数组来说,单调栈的操作复杂度是O(n)。这保证了整体的时间复杂度是线性的,从而在时间上是可接受的。
🦆
题解中计算子数组长度`k = r - l - 1`的合理性在哪里?为什么要从减去l再减去1?
在题解中,`l`和`r`分别表示当前元素左右两侧第一个小于它的元素的索引。因此,子数组的实际范围是从`l+1`到`r-1`(包括两端点)。计算这个范围内元素的数量,即长度`k`,应该用`r - (l + 1)`。简化这个表达式就是`r - l - 1`。这样计算出的`k`是当前元素为最小值时所能达到的最大子数组长度,合理地反映了题目要求的子数组的边界和长度。

相关问题