<p>You are given an integer array <code>nums</code> and an integer <code>threshold</code>.</p>

<p>Find any subarray of <code>nums</code> of length <code>k</code> such that <strong>every</strong> element in the subarray is <strong>greater</strong> than <code>threshold / k</code>.</p>

<p>Return<em> the <strong>size</strong> of <strong>any</strong> such subarray</em>. If there is no such subarray, return <code>-1</code>.</p>

<p>A <strong>subarray</strong> is a contiguous non-empty sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,4,3,1], threshold = 6
<strong>Output:</strong> 3
<strong>Explanation:</strong> The subarray [3,4,3] has a size of 3, and every element is greater than 6 / 3 = 2.
Note that this is the only valid subarray.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,5,6,5,8], threshold = 7
<strong>Output:</strong> 1
<strong>Explanation:</strong> The subarray [8] has a size of 1, and 8 &gt; 7 / 1 = 7. So 1 is returned.
Note that the subarray [6,5] has a size of 2, and every element is greater than 7 / 2 = 3.5. 
Similarly, the subarrays [6,5,6], [6,5,6,5], [6,5,6,5,8] also satisfy the given conditions.
Therefore, 2, 3, 4, or 5 may also be returned.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], threshold &lt;= 10<sup>9</sup></code></li>
</ul>

#2024/09/18
'''
1,3,4,3,1 6
3 3,4,3 >2

5
l=1
r=1
https://leetcode.cn/problems/subarray-with-elements-greater-than-varying-threshold/solutions/1658410/by-endlesscheng-j6pp/
对于每一段，我们只需要检查这一段里面最小的那个数满不满足条件。如果最小的数满足条件，那么这一段就可以

所以，要去找每一个数作为最小的这个数的那一段的边界。也就是要找到它左边第一个比他小的和右边第一个比他小的-》单调栈

假设左边没有比他小的left=[-1]*n
维护一个stack，这个stack里面存idx,从左往右遍历。当前如果小于等于stack，说明stack里面存的都没有用了（对于未来的数来说，当前可以作为边界），
所以拿出来。拿出来以后stack还有，说明这个数就是当前遍历到的num的左边界。然后把当前idx放进去： 维护一个单调递增的栈

右边同理

这样以后，对于每一个num，都能O(1)得到以它作为最小值的那一段的长度。所以只要它大于threshod/k，那么这一段都满足。返回就好了
'''
class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        
        # left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        left = [-1] * n
        st = []
        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[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        right = [n] * n
        st = []
        for i in reversed(range(n)):
            while st and nums[st[-1]] >= nums[i]:
                st.pop()
            if st:
                right[i] = st[-1]
            st.append(i)

        # 检查是否存在有效的子数组
        for i in range(n):
            num = nums[i]
            l = left[i]
            r = right[i]
            k = r - l - 1
            if num > threshold // k:
                return k
        return -1
896