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 <= 1051 <= nums[i], threshold <= 109
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| 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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 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
}
|
