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.
1import java.util.ArrayList;
2import java.
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.