2334. 元素值大于变化阈值的子数组-单调栈法和暴力求解法
数组 元素 变化 求解 暴力 大于 单调 阈值
2023-09-14 09:06:52 时间
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 都可以。
int validSubarraySize(int* nums, int numsSize, int threshold){
for(int i=0;i<numsSize;i++){
int now_num=nums[i];
int j;
int len=0;
if(i>0){
if(nums[i]==nums[i-1]){
continue;
}
}
for(j=i+1;j<numsSize;j++){
if(nums[j]<now_num){
break;
}
}
len=len+j-i-1;
for( j=i-1;j>=0;j--){
if(nums[j]<now_num){
break;
}
}
len=i-j+len;
// printf("%d ",len);
if(threshold/len<now_num){
return len;
}
}
return -1;
}
单调栈法如下:
int validSubarraySize(int* nums, int numsSize, int threshold){
int right_snaller[numsSize],left_smaller[numsSize];
int stack[numsSize];
int index=0;
int top=0;
while(index!=numsSize){
while(top!=0){
if(nums[stack[top-1]]>nums[index]){
right_snaller[stack[--top]]=index;
}
else{
break;
}
}
stack[top++]=index;
index++;
}
while(top!=0){
right_snaller[stack[--top]]=-1;
}
index=numsSize-1;
while(index!=-1){
while(top!=0){
if(nums[stack[top-1]]>nums[index]){
left_smaller[stack[--top]]=index;
}
else{
break;
}
}
stack[top++]=index;
index--;
}
while(top!=0){
left_smaller[stack[--top]]=-1;
}
for(int i=0;i<numsSize;i++){
int r=right_snaller[i],l=left_smaller[i];
if(r==-1){
r=numsSize;
}
if(l==-1){
l=-1;
}
int len=r-l-1;
if(nums[i]>threshold/len){
return len;
}
// printf("%d %d ||",right_snaller[i],left_smaller[i]);
}
return -1;
}
相关文章
- Perl快捷删除数组重复元素
- float型数据与字节数组的转化
- 每日一道 LeetCode (8):删除排序数组中的重复项和移除元素
- Python简单计算数组元素平均值的方法示例
- 向数组中添加一个元素
- 462. 最小操作次数使数组元素相等 II——【Leetcode每日一题】
- Leetcode540: 有序数组中的单一元素(medium)
- Scala数组元素的修改update
- js 数组后面追加一个数组,连接数组,数组添加元素
- 最长连续序列-c语言哈希表加数组界定法
- 2.2 数组列表
- 习题 9.4 建立一个对象数组,内放5个学生的数据(学号、成绩),用指针指向数组首元素,输出第1,3,5个学生的数据。
- 习题 6.8 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大、在该列上最小。也可能没有鞍点。
- 例 8.12 有一个3*4的二维数组,要求用指向元素的指针变量输出二维数组各元素的值。
- 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
- Leetcode 1464. 数组中两元素的最大乘积
- VB编程:利用指针实现数组的插入-43_彭世瑜_新浪博客
- Go语言自学系列 | go语言访问数组元素
- 5.5 bisect--数组的二分算法
- 输出二维数组各元素的值第二版
- golang删除数组某个元素
- Array 数组去重 总结10方法(7)
- tensorflow 动态数组 TensorArray
- C语言进阶-可变数组