1
class Solution {
2
  public int validSubarraySize(int[] nums, int threshold) {
3
    int n = nums.length;
4
    int[] next_small = new int[n];
5
    int[] prev_small = new int[n];
6
    Stack<Integer> stack = new Stack<>();
7
    stack.push(0);
8
    Arrays.fill(next_small, n);
9
    Arrays.fill(prev_small, -1);
10
    for (int i = 1; i < n; i++) {
11
      while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
12
        stack.pop();
13
      }
14
      if (stack.size() != 0) {
15
        prev_small[i] = stack.peek();
16
      }
17
      stack.push(i);
18
    }
19
    stack = new Stack<>();
20
    stack.push(n - 1);
21
    for (int i = n - 2; i >= 0; i--) {
22
      while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
23
        stack.pop();
24
      }
25
      if (stack.size() != 0) {
26
        next_small[i] = stack.peek();
27
      }
28
      stack.push(i);
29
    }
30
    for (int i = 0; i < n; i++) {
31
      int len = next_small[i] - prev_small[i] - 1;
32
      if (threshold / (double) len < nums[i]) {
33
        return len;
34
      }
35
    }
36
    return -1;
37
  }
38
}