Question

2334. Subarray With Elements Greater Than Varying Threshold

中文文档

Description

You are given an integer array nums and an integer threshold.

Find any subarray of nums of length k such that every element in the subarray is greater than threshold / k.

Return_ the size of any such subarray_. If there is no such subarray, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,4,3,1], threshold = 6
Output: 3
Explanation: 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.

Example 2:

Input: nums = [6,5,6,5,8], threshold = 7
Output: 1
Explanation: The subarray [8] has a size of 1, and 8 > 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.

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def validSubarraySize(self, nums: List[int], threshold: int) -> int:
    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    def merge(a, b):
      pa, pb = find(a), find(b)
      if pa == pb:
        return
      p[pa] = pb
      size[pb] += size[pa]

    n = len(nums)
    p = list(range(n))
    size = [1] * n
    arr = sorted(zip(nums, range(n)), reverse=True)
    vis = [False] * n
    for v, i in arr:
      if i and vis[i - 1]:
        merge(i, i - 1)
      if i < n - 1 and vis[i + 1]:
        merge(i, i + 1)
      if v > threshold // size[find(i)]:
        return size[find(i)]
      vis[i] = True
    return -1

class Solution {
  private int[] p;
  private int[] size;

  public int validSubarraySize(int[] nums, int threshold) {
    int n = nums.length;
    p = new int[n];
    size = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      size[i] = 1;
    }
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; ++i) {
      arr[i][0] = nums[i];
      arr[i][1] = i;
    }
    Arrays.sort(arr, (a, b) -> b[0] - a[0]);
    boolean[] vis = new boolean[n];
    for (int[] e : arr) {
      int v = e[0], i = e[1];
      if (i > 0 && vis[i - 1]) {
        merge(i, i - 1);
      }
      if (i < n - 1 && vis[i + 1]) {
        merge(i, i + 1);
      }
      if (v > threshold / size[find(i)]) {
        return size[find(i)];
      }
      vis[i] = true;
    }
    return -1;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }

  private void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return;
    }
    p[pa] = pb;
    size[pb] += size[pa];
  }
}

using pii = pair<int, int>;

class Solution {
public:
  vector<int> p;
  vector<int> size;

  int validSubarraySize(vector<int>& nums, int threshold) {
    int n = nums.size();
    p.resize(n);
    for (int i = 0; i < n; ++i) p[i] = i;
    size.assign(n, 1);
    vector<pii> arr(n);
    for (int i = 0; i < n; ++i) arr[i] = {nums[i], i};
    sort(arr.begin(), arr.end());
    vector<bool> vis(n);
    for (int j = n - 1; ~j; --j) {
      int v = arr[j].first, i = arr[j].second;
      if (i && vis[i - 1]) merge(i, i - 1);
      if (j < n - 1 && vis[i + 1]) merge(i, i + 1);
      if (v > threshold / size[find(i)]) return size[find(i)];
      vis[i] = true;
    }
    return -1;
  }

  int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
  }

  void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) return;
    p[pa] = pb;
    size[pb] += size[pa];
  }
};

func validSubarraySize(nums []int, threshold int) int {
  n := len(nums)
  p := make([]int, n)
  size := make([]int, n)
  for i := range p {
    p[i] = i
    size[i] = 1
  }
  var find func(int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  merge := func(a, b int) {
    pa, pb := find(a), find(b)
    if pa == pb {
      return
    }
    p[pa] = pb
    size[pb] += size[pa]
  }

  arr := make([][]int, n)
  for i, v := range nums {
    arr[i] = []int{v, i}
  }
  sort.Slice(arr, func(i, j int) bool {
    return arr[i][0] > arr[j][0]
  })
  vis := make([]bool, n)
  for _, e := range arr {
    v, i := e[0], e[1]
    if i > 0 && vis[i-1] {
      merge(i, i-1)
    }
    if i < n-1 && vis[i+1] {
      merge(i, i+1)
    }
    if v > threshold/size[find(i)] {
      return size[find(i)]
    }
    vis[i] = true
  }
  return -1
}

Solution 2

class Solution:
  def validSubarraySize(self, nums: List[int], threshold: int) -> int:
    n = len(nums)
    left = [-1] * n
    right = [n] * n
    stk = []
    for i, v in enumerate(nums):
      while stk and nums[stk[-1]] >= v:
        stk.pop()
      if stk:
        left[i] = stk[-1]
      stk.append(i)
    stk = []
    for i in range(n - 1, -1, -1):
      while stk and nums[stk[-1]] >= nums[i]:
        stk.pop()
      if stk:
        right[i] = stk[-1]
      stk.append(i)
    for i, v in enumerate(nums):
      k = right[i] - left[i] - 1
      if v > threshold // k:
        return k
    return -1

class Solution {
  public int validSubarraySize(int[] nums, int threshold) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    Arrays.fill(left, -1);
    Arrays.fill(right, n);
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      while (!stk.isEmpty() && nums[stk.peek()] >= v) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        left[i] = stk.peek();
      }
      stk.push(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; --i) {
      int v = nums[i];
      while (!stk.isEmpty() && nums[stk.peek()] >= v) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        right[i] = stk.peek();
      }
      stk.push(i);
    }
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      int k = right[i] - left[i] - 1;
      if (v > threshold / k) {
        return k;
      }
    }
    return -1;
  }
}

class Solution {
public:
  int validSubarraySize(vector<int>& nums, int threshold) {
    int n = nums.size();
    vector<int> left(n, -1);
    vector<int> right(n, n);
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      while (!stk.empty() && nums[stk.top()] >= v) stk.pop();
      if (!stk.empty()) left[i] = stk.top();
      stk.push(i);
    }
    stk = stack<int>();
    for (int i = n - 1; ~i; --i) {
      int v = nums[i];
      while (!stk.empty() && nums[stk.top()] >= v) stk.pop();
      if (!stk.empty()) right[i] = stk.top();
      stk.push(i);
    }
    for (int i = 0; i < n; ++i) {
      int v = nums[i];
      int k = right[i] - left[i] - 1;
      if (v > threshold / k) return k;
    }
    return -1;
  }
};

func validSubarraySize(nums []int, threshold int) int {
  n := len(nums)
  left := make([]int, n)
  right := make([]int, n)
  for i := range left {
    left[i] = -1
    right[i] = n
  }
  var stk []int
  for i, v := range nums {
    for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      left[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  stk = []int{}
  for i := n - 1; i >= 0; i-- {
    v := nums[i]
    for len(stk) > 0 && nums[stk[len(stk)-1]] >= v {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      right[i] = stk[len(stk)-1]
    }
    stk = append(stk, i)
  }
  for i, v := range nums {
    k := right[i] - left[i] - 1
    if v > threshold/k {
      return k
    }
  }
  return -1
}