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.
1#include <vector>
2#include <stack>
3#include <algorithm>
4
5int maxWidthRamp(std::vector<int>& nums) {
6 std::stack<int> s;
7 int max_width = 0;
8
9 for (int i = 0; i < nums.size(); ++i) {
10 if (s.empty() || nums[s.top()] > nums[i]) {
11 s.push(i);
12 }
13 }
14
15 for (int j = nums.size() - 1; j >= 0; --j) {
16 while (!s.empty() && nums[s.top()] <= nums[j]) {
17 max_width = std::max(max_width, j - s.top());
18 s.pop();
19 }
20 }
21
22 return max_width;
23}This solution uses a stack to build a sequence of indices with decreasing values. When processing from the end of the array, it finds the maximum possible width for ramps using these indices.
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.