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.
1import java.util.ArrayList;
2import java.util
This solution sorts the indices based on their values and then iteratively updates the maximum width by finding the smallest index encountered so far, to ensure the widest ramp.