2334. Subarray With Elements Greater Than Varying Threshold
Tags:
Hard
Skills:
Monotonic stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach
Solution 1: TC: O(n), SC: O(n)
Input: nums = [1,3,4,3,1], threshold = 6
Output: 31function 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};Đây là công thức được sử dụng để tính độ dài của subarray mà phần tử nums[i] là giá trị nhỏ nhất.
Ý nghĩa của mảng left_smaller và right_smaller
Khoảng subarray mà nums[i] là giá trị nhỏ nhất:
k = (right_smaller[i] - 1) - (left_smaller[i] + 1) + 1
k = right_smaller[i] - left_smaller[i] - 1;
Solution 2: TC: O(n), SC: O(n) - Optimize
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