2334. Subarray With Elements Greater Than Varying Threshold

Input: nums = [1,3,4,3,1], threshold = 6
Output: 3

1function validSubarraySize(nums: number[], threshold: number): number {
2    const n = nums.length;
3    const left_smaller: number[] = new Array(n).fill(-1);
4    const right_smaller: number[] = new Array(n).fill(n);
5    
6    for(let i = 0; i < n; i++) {
7	    while(stack.length > 0 && nums[stack.at(-1)] >= nums[i]) {
8		    stack.pop();
9	    }
10	    if(stack.length > 0) {
11		    left_smaller[i] = stack.at(-1);
12	    }
13	    stack.push(i);
14    }
15    
16    for (let i = n - 1; i >= 0; i--) {
17	    while(stack.length > 0 && nums[stack.at(-1)] >= nums[i]) {
18		    stack.pop();
19	    }
20	    if(stack.length > 0) {
21		    right_smaller[i] = stack.at(-1);
22	    }
23	    stack.push(i);
24    }
25    
26    for(let i = 0; i < n; i++) {
27	    const k = right_smaller[i] - left_smaller[i] - 1;
28	    if(nums[i] > threshold / k) {
29		    return k;
30	    }
31    }
32
33		return -1;
34};

1function validSubarraySize(nums: number[], threshold: number): number {
2    const n = nums.length;
3    const stack: number[] = [];
4    const thresholdValues = new Array(n + 1).fill(0);
5
6    // Tiền xử lý giá trị threshold / k
7    for (let k = 1; k <= n; k++) {
8        thresholdValues[k] = threshold / k;
9    }
10
11    // Duyệt từ trái sang phải, đồng thời tính right_smaller
12    for (let i = 0; i < n; i++) {
13        while (stack.length > 0 && nums[stack[stack.length - 1]] >= nums[i]) {
14            const idx = stack.pop()!;
15            const k = i - (stack.length > 0 ? stack[stack.length - 1] + 1 : 0);
16            if (nums[idx] > thresholdValues[k]) {
17                return k;
18            }
19        }
20        stack.push(i);
21    }
22
23    // Xử lý phần còn lại trong stack
24    while (stack.length > 0) {
25        const idx = stack.pop()!;
26        const k = n - (stack.length > 0 ? stack[stack.length - 1] + 1 : 0);
27        if (nums[idx] > thresholdValues[k]) {
28            return k;
29        }
30    }
31
32    return -1;
33}
34