2334-元素值大于变化阈值的子数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

给你一个整数数组 nums 和一个整数 threshold 。

找到长度为 k 的 nums 子数组，满足数组中 每个 元素都 大于 threshold / k 。

请你返回满足要求的 任意 子数组的 大小 。如果没有这样的子数组，返回 -1 。

子数组 是数组中一段连续非空的元素序列。

示例 1：

**输入：** nums = [1,3,4,3,1], threshold = 6
**输出：** 3
**解释：** 子数组 [3,4,3] 大小为 3 ，每个元素都大于 6 / 3 = 2 。
注意这是唯一合法的子数组。

示例 2：

**输入：** nums = [6,5,6,5,8], threshold = 7
**输出：** 1
**解释：** 子数组 [8] 大小为 1 ，且 8 > 7 / 1 = 7 。所以返回 1 。
注意子数组 [6,5] 大小为 2 ，每个元素都大于 7 / 2 = 3.5 。
类似的，子数组 [6,5,6] ，[6,5,6,5] ，[6,5,6,5,8] 都是符合条件的子数组。
所以返回 2, 3, 4 和 5 都可以。

提示：

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

本题 视频讲解 已出炉，欢迎点赞三连~

方法一：并查集

提示 1

数组中的元素越大越好，不妨从大往小考虑 nums}[i]。

提示 2

子数组的长度 k 越大，\dfrac{\textit{threshold} }{k 就越小，越能满足要求。

提示 3

把考虑过的元素都串起来，这条链的长度就是 k。

于是关键在于如何动态维护每条链的长度，高效地串联两条链。

提示 4

用并查集，遍历到 nums}[i] 时，用并查集合并 i 和 i+1，这样可以把连续访问过的位置串起来，同时维护链的长度。

复杂度分析

  • 时间复杂度：O(n\log n)。瓶颈在排序上。
  • 空间复杂度：O(n)。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        fa = list(range(n + 1))
        sz = [0] * (n + 1)
        def find(x: int) -> int:
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        for num, i in sorted(zip(nums, range(n)), reverse=True):
            j = find(i + 1)
            fa[i] = j  # 合并 i 和 i+1
            sz[j] += sz[i] + 1
            if num > threshold // sz[j]: return sz[j]
        return -1
[sol1-Java]
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
class Solution {
    int[] fa;

    public int validSubarraySize(int[] nums, int threshold) {
        var n = nums.length;
        fa = new int[n + 1];
        for (var i = 0; i <= n; i++) fa[i] = i;
        var sz = new int[n + 1];

        var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(ids, (i, j) -> nums[j] - nums[i]);
        for (var i : ids) {
            var j = find(i + 1);
            fa[i] = j; // 合并 i 和 i+1
            sz[j] += sz[i] + 1;
            if (nums[i] > threshold / sz[j]) return sz[j];
        }
        return -1;
    }

    int find(int x) {
        if (fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int validSubarraySize(vector<int> &nums, int threshold) {
        int n = nums.size();
        int fa[n + 1], sz[n + 1];
        iota(fa, fa + n + 1, 0);
        memset(sz, 0, sizeof(sz));
        function<int(int)> find = [&](int x) -> int { return fa[x] == x ? x : fa[x] = find(fa[x]); };

        int ids[n];
        iota(ids, ids + n, 0);
        sort(ids, ids + n, [&](int i, int j) { return nums[i] > nums[j]; });
        for (int i : ids) {
            int j = find(i + 1);
            fa[i] = j; // 合并 i 和 i+1
            sz[j] += sz[i] + 1;
            if (nums[i] > threshold / sz[j]) return sz[j];
        }
        return -1;
    }
};
[sol1-Go]
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
func validSubarraySize(nums []int, threshold int) int {
	n := len(nums)
	type pair struct{ v, i int }
	a := make([]pair, n)
	for i, v := range nums {
		a[i] = pair{v, i}
	}
	sort.Slice(a, func(i, j int) bool { return a[i].v > a[j].v })

	fa := make([]int, n+1)
	for i := range fa {
		fa[i] = i
	}
	sz := make([]int, n+1)
	var find func(int) int
	find = func(x int) int {
		if fa[x] != x {
			fa[x] = find(fa[x])
		}
		return fa[x]
	}
	for _, p := range a {
		i := p.i
		j := find(i + 1)
		fa[i] = j // 合并 i 和 i+1
		sz[j] += sz[i] + 1
		if p.v > threshold/sz[j] {
			return sz[j]
		}
	}
	return -1
}

方法二：单调栈

提示 1

枚举每个元素，假设它是子数组中的最小值。

提示 2

子数组的左右边界最远能到哪？

提示 3

用单调栈来计算左右边界。

不了解单调栈的同学可以看一下 496. 下一个更大元素 I 。本题求的是更小元素。

知道了左右边界也就知道了子数组的长度 k。

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        left, st = [-1] * n, []  # left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        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, st = [n] * n, []  # right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        for i in range(n - 1, -1, -1):
            while st and nums[st[-1]] >= nums[i]: st.pop()
            if st: right[i] = st[-1]
            st.append(i)

        for num, l, r in zip(nums, left, right):
            k = r - l - 1
            if num > threshold // k: return k
        return -1
[sol1-Java]
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
class Solution {
    public int validSubarraySize(int[] nums, int threshold) {
        var n = nums.length;
        var left = new int[n]; // left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        var st = new ArrayDeque<Integer>();
        for (var i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop();
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        var right = new int[n]; // right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        st = new ArrayDeque<>();
        for (var i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && nums[st.peek()] >= nums[i]) st.pop();
            right[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        for (var i = 0; i < n; ++i) {
            var k = right[i] - left[i] - 1;
            if (nums[i] > threshold / k) return k;
        }
        return -1;
    }
}
[sol1-C++]
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
class Solution {
public:
    int validSubarraySize(vector<int> &nums, int threshold) {
        int n = nums.size();
        int left[n]; // left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && nums[s.top()] >= nums[i]) s.pop();
            left[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }

        int right[n]; // right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
        s = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!s.empty() && nums[s.top()] >= nums[i]) s.pop();
            right[i] = s.empty() ? n : s.top();
            s.push(i);
        }

        for (int i = 0; i < n; ++i) {
            int k = right[i] - left[i] - 1;
            if (nums[i] > threshold / k) return k;
        }
        return -1;
    }
};
[sol1-Go]
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
func validSubarraySize(nums []int, threshold int) int {
	n := len(nums)
	left := make([]int, n) // left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）
	st := []int{-1}
	for i, v := range nums {
		for len(st) > 1 && nums[st[len(st)-1]] >= v {
			st = st[:len(st)-1]
		}
		left[i] = st[len(st)-1]
		st = append(st, i)
	}

	right := make([]int, n) // right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）
	st = []int{n}
	for i := n - 1; i >= 0; i-- {
		for len(st) > 1 && nums[st[len(st)-1]] >= nums[i] {
			st = st[:len(st)-1]
		}
		right[i] = st[len(st)-1]
		st = append(st, i)
	}

	for i, num := range nums {
		k := right[i] - left[i] - 1
		if num > threshold/k {
			return k
		}
	}
	return -1
}
 Comments
On this page
2334-元素值大于变化阈值的子数组
  1. 方法一：并查集