---
# System prepended metadata

title: 2334. Subarray With Elements Greater Than Varying Threshold
tags: [Leetcode, Monotonic Stack, Hard]

---

# 2334. Subarray With Elements Greater Than Varying Threshold
###### tags: `Leetcode` `Hard` `Monotonic Stack`
Link: https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold/
## 思路
参考[这里](https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold/discuss/2259557/Monostack)
首先计算出the minimum size of the subarray that includes $nums[i]$，也就是$(threshold/nums[i])+1$，替代nums
这样用单调栈 找next large，因为出现next large就说明可以检查一下next large之前的subarray是不是valid
这里$cnt$的初始值是$0$不是$1$的原因是由于当下的num可能是next large，所以要先看一下前面满不满足条件（有可能加上next large就不满足条件了）
## Code
```java=
class Solution {
    public int validSubarraySize(int[] nums, int threshold) {
        for(int i=0; i<nums.length; i++){
            nums[i] = threshold/nums[i] + 1;
        } 
        Stack<int[]> stack = new Stack<>();
        for(int i=0; i<=nums.length; i++){
            int num = i==nums.length?Integer.MAX_VALUE:nums[i];
            int cnt = 0;
            while(!stack.isEmpty() && stack.peek()[0]<=num){
                cnt += stack.peek()[1];
                if(cnt >= stack.peek()[0]) return cnt;
                stack.pop();
            }
            stack.push(new int[]{num, cnt+1});
        }
        return -1;
    }
}
```