LC 6119. 元素值大于变化阈值的子数组
这提的思路就是，对于 `A[i]` 来说，如果它是最小值，那么它左右可以覆盖的范围是多少。假设我们对于左边进行考虑
- 如果 A[i] <= A[j], 而 A[j] 覆盖的范围是 l, 那么A[i]至少可以覆盖到l. 那么A[i] 继续和 A[l]进行比较
- 如果 A[i] > A[l], 那么 A[i] 覆盖的范围就是到 l.
这个算法我不知道具体时间复杂度是多少，可能会遇到某些极端情况，但是对于递增/递减序列都可以很容易应对。
class Solution:
def validSubarraySize(self, nums: List[int], threshold: int) -> int:
n = len(nums)
A = [-1] * n
for i in range(1, n):
j = i - 1
while j >= 0 and nums[i] <= nums[j]:
j = A[j]
A[i] = j
B = [n] * n
for i in reversed(range(n - 1)):
j = i + 1
while j < n and nums[i] <= nums[j]:
j = B[j]
B[i] = j
for i in range(n):
sz = B[i] - A[i] - 1
if nums[i] * sz > threshold:
return sz
return -1