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

标签: 栈 并查集 数组 单调栈

难度: Hard

给你一个整数数组 nums 和一个整数 threshold 。

找到长度为 k 的 nums 子数组，满足数组中 每个 元素都 大于 threshold / k 。

请你返回满足要求的 任意 子数组的 大小 。如果没有这样的子数组，返回 -1 。

子数组 是数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,3,4,3,1], threshold = 6
输出：3
解释：子数组 [3,4,3] 大小为 3 ，每个元素都大于 6 / 3 = 2 。
注意这是唯一合法的子数组。

示例 2：

输入：nums = [6,5,6,5,8], threshold = 7
输出：1
解释：子数组 [8] 大小为 1 ，且 8 > 7 / 1 = 7 。所以返回 1 。
注意子数组 [6,5] 大小为 2 ，每个元素都大于 7 / 2 = 3.5 。
类似的，子数组 [6,5,6] ，[6,5,6,5] ，[6,5,6,5,8] 都是符合条件的子数组。
所以返回 2, 3, 4 和 5 都可以。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i], threshold <= 109

Submission

运行时间: 163 ms

内存: 29.1 MB

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        left, st = [-1] * n, []  # left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        for i, v in enumerate(nums):
            while st and nums[st[-1]] >= v: st.pop()
            if st: left[i] = st[-1]
            st.append(i)

        right, st = [n] * n, []  # right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] >= nums[i]: st.pop()
            if st: right[i] = st[-1]
            st.append(i)

        for num, l, r in zip(nums, left, right):
            k = r - l - 1
            if num > threshold // k: return k
        return -1

Explain

这个题解首先利用单调栈来预处理出每个元素左右两侧第一个小于它的元素的位置。这样做的目的是为了快速找出以当前元素为最小值的最大可能子数组的长度。然后，该解法遍历整个数组，对于每个元素，计算如果以该元素为最小值时，能形成的最大子数组的长度k，然后检查该元素是否满足条件 num > threshold / k。如果满足，即返回k作为结果。如果遍历完数组都没有找到符合条件的子数组，最终返回-1。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        left, st = [-1] * n, []  # left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        for i, v in enumerate(nums):
            while st and nums[st[-1]] >= v: st.pop()  # 维护栈的单调递减性
            if st: left[i] = st[-1]
            st.append(i)

        right, st = [n] * n, []  # right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] >= nums[i]: st.pop()  # 维护栈的单调递减性
            if st: right[i] = st[-1]
            st.append(i)

        for num, l, r in zip(nums, left, right):
            k = r - l - 1  # 计算以 num 为最小值的最大可能子数组长度
            if num > threshold // k: return k  # 检查是否满足条件
        return -1  # 如果没有找到符合条件的子数组，返回-1

Explore

题解中使用单调栈的目的是为了快速确定每个元素左右两边第一个小于它的元素的位置。这种信息对于确定以当前元素为最小值的最大可能子数组的长度是非常有用的。单调栈通过维护一个元素索引的栈，确保栈内的元素值是单调递减的，使得当遍历到新的元素时，可以快速找到栈顶元素为最近的、且比当前元素小的元素。如果新元素小于栈顶元素，就弹出栈顶，这样可以保持栈的单调性。这种结构使得每个元素被压入和弹出栈的操作最多各发生一次，从而高效地预处理出所需的位置信息。

单调栈的操作复杂度是非常高效的。每个元素最多被压入和弹出栈一次，因此遍历整个数组的过程中，每个元素的进栈和出栈操作的总次数是常数，即O(1)。因此，对于整个数组来说，单调栈的操作复杂度是O(n)。这保证了整体的时间复杂度是线性的，从而在时间上是可接受的。

在题解中，`l`和`r`分别表示当前元素左右两侧第一个小于它的元素的索引。因此，子数组的实际范围是从`l+1`到`r-1`（包括两端点）。计算这个范围内元素的数量，即长度`k`，应该用`r - (l + 1)`。简化这个表达式就是`r - l - 1`。这样计算出的`k`是当前元素为最小值时所能达到的最大子数组长度，合理地反映了题目要求的子数组的边界和长度。