class Solution {
public:
int validSubarraySize(vector<int>& nums, int threshold) {
}
};
2334. 元素值大于变化阈值的子数组
给你一个整数数组 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 <= 1051 <= nums[i], threshold <= 109原站题解
golang 解法, 执行用时: 180 ms, 内存消耗: 10.3 MB, 提交时间: 2023-09-19 16:59:37
// 并查集
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
}
// 单调栈
func validSubarraySize2(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
}
cpp 解法, 执行用时: 216 ms, 内存消耗: 91.8 MB, 提交时间: 2023-09-19 16:58:43
class Solution {
public:
// 并查集
int validSubarraySize2(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;
}
// 单调栈
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;
}
};
java 解法, 执行用时: 111 ms, 内存消耗: 55.1 MB, 提交时间: 2023-09-19 16:57:46
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];
}
// 单调栈
public int validSubarraySize2(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;
}
}
python3 解法, 执行用时: 564 ms, 内存消耗: 48.2 MB, 提交时间: 2023-09-19 16:56:45
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
# 单调栈
def validSubarraySize2(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