2334. 元素值大于变化阈值的子数组-单调栈法和暴力求解法

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;

}
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

单调栈法如下：

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;

}
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
52
53
54
55
56
57
58
59
60
61
62
63
64