Sponsored
Sponsored
This approach utilizes a stack to keep track of indices in a monotonically decreasing order, which helps to quickly find the maximum possible ramp width.
Time Complexity: O(n), where n is the number of elements in the array - because each element is pushed and popped from the stack at most once.
Space Complexity: O(n) for the stack of indices.
1def maxWidthRamp(nums):
2 stack = []
3 max_width = 0
4
5 # Build initial decreasing stack of indices
6 for i, num in enumerate(nums):
7 if not stack or nums[stack[-1]] > num:
8 stack.append(i)
9
10 # Traverse from the end for maximum width
11 for j in range(len(nums) - 1, -1, -1):
12 while stack and nums[stack[-1]] <= nums[j]:
13 max_width = max(max_width, j - stack.pop())
14
15 return max_widthThis solution first creates a stack that holds indices of nums in a decreasing manner. It then traverses the array from right to left, popping elements from the stack to calculate potential maximum widths.
This approach uses two pointers to find the maximum width ramp by initially sorting potential endpoints and then finding the earliest start point that forms a valid ramp.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaxWidthRamp(int[] nums) {
6 List<int> indices = new List<int>();
for (int i = 0; i < nums.Length; i++) {
indices.Add(i);
}
indices.Sort((a, b) => nums[a] - nums[b]);
int maxRamp = 0;
int minIndex = nums.Length;
foreach (int index in indices) {
maxRamp = Math.Max(maxRamp, index - minIndex);
minIndex = Math.Min(minIndex, index);
}
return maxRamp;
}
}The code sorts the indices of the array and then calculates the maximum width possible by checking the minimum index encountered in this sorted order.