962. Maximum Width Ramp
Tags:
Medium
Skills:
StackMonotonic stack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm độ rộng tối đa của một đoạn dốc (ramp) trong mảng số nguyên nums. Một đoạn dốc (i, j) thỏa mãn:
Độ rộng của đoạn dốc được định nghĩa là j - i. Nếu không có đoạn dốc nào, return 0
Approach - Brute force
Approach - Stack
Time and space complexity
Solution - stack
1function maxWidthRamp(nums: number[]): number {
2 let stack: number[] = [];
3 let n = nums.length;
4 let max_width = 0;
5
6 for (let i = 0; i < n; i++) {
7 if (stack.length === 0 || nums[stack.at(-1)] > nums[i]) {
8 stack.push(i);
9 }
10 }
11
12 for (let i = n - 1; i >= 0; i--) {
13 while (stack.length > 0 && nums[stack.at(-1)] <= nums[i]) {
14 max_width = Math.max(max_width, i - stack.pop());
15 }
16
17 if (stack.length === 0) {
18 break;
19 }
20 }
21 return max_width;
22};