Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/962.html
962. Maximum Width Ramp (Medium)
Given an array A
of integers, a ramp is a tuple (i, j)
for which i < j
and A[i] <= A[j]
. The width of such a ramp is j - i
.
Find the maximum width of a ramp in A
. If one doesn't exist, return 0.
Example 1:
Input: [6,0,8,2,1,5] Output: 4 Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.
Example 2:
Input: [9,8,1,0,1,9,4,0,4,1] Output: 7 Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.
Note:
2 <= A.length <= 50000
0 <= A[i] <= 50000
Related Topics:
Array
Solution 1.
Consider the array ends with 4, 1, 2
. For the a number n
in front:
- If
n <= 2
, we use the last2
to form the ramp. The last1
won’t be used. - If
2 < n <= 4
, we use the last4
to form the ramp.
So we can traverse from rear to front, and save the numbers in ascending order:
numbers: [2, 4]
indexes: [N - 1, N - 3]
Then we traverse from front to rear, use lower_bound
to find the smallest number greater than the current A[i]
. The corresponding index
can be used form a ramp.
// OJ: https://leetcode.com/problems/maximum-width-ramp/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
int N = A.size(), ans = 0;
vector<int> v, index;
for (int i = N - 1; i >= 0; --i) {
if (v.empty() || v.back() < A[i]) {
v.push_back(A[i]);
index.push_back(i);
}
}
for (int i = 0; i < N; ++i) {
int ind = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
ans = max(ans, index[ind] - i);
}
return ans;
}
};
-
class Solution { public int maxWidthRamp(int[] A) { if (A == null || A.length < 2) return 0; int maxWidth = 0; Stack<Integer> numStack = new Stack<Integer>(); Stack<Integer> indicesStack = new Stack<Integer>(); numStack.push(A[0]); indicesStack.push(0); int length = A.length; for (int i = 1; i < length; i++) { int num = A[i]; if (numStack.isEmpty() || num < numStack.peek()) { numStack.push(num); indicesStack.push(i); } else { Stack<Integer> tempNumStack = new Stack<Integer>(); Stack<Integer> tempIndicesStack = new Stack<Integer>(); while (!numStack.isEmpty() && num >= numStack.peek()) { tempNumStack.push(numStack.pop()); tempIndicesStack.push(indicesStack.pop()); } int prevIndex = tempIndicesStack.peek(); maxWidth = Math.max(maxWidth, i - prevIndex); while (!tempNumStack.isEmpty()) { numStack.push(tempNumStack.pop()); indicesStack.push(tempIndicesStack.pop()); } } } return maxWidth; } } ############ class Solution { public int maxWidthRamp(int[] nums) { int n = nums.length; Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { if (stk.isEmpty() || nums[stk.peek()] > nums[i]) { stk.push(i); } } int ans = 0; for (int i = n - 1; i >= 0; --i) { while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) { ans = Math.max(ans, i - stk.pop()); } if (stk.isEmpty()) { break; } } return ans; } }
-
// OJ: https://leetcode.com/problems/maximum-width-ramp/ // Time: O(NlogN) // Space: O(N) class Solution { public: int maxWidthRamp(vector<int>& A) { int N = A.size(), ans = 0; vector<int> v, index; for (int i = N - 1; i >= 0; --i) { if (v.empty() || v.back() < A[i]) { v.push_back(A[i]); index.push_back(i); } } for (int i = 0; i < N; ++i) { int ind = lower_bound(v.begin(), v.end(), A[i]) - v.begin(); ans = max(ans, index[ind] - i); } return ans; } };
-
class Solution: def maxWidthRamp(self, nums: List[int]) -> int: stk = [] for i, v in enumerate(nums): if not stk or nums[stk[-1]] > v: stk.append(i) ans = 0 for i in range(len(nums) - 1, -1, -1): while stk and nums[stk[-1]] <= nums[i]: ans = max(ans, i - stk.pop()) if not stk: break return ans ############ class Solution(object): def maxWidthRamp(self, A): """ :type A: List[int] :rtype: int """ N = len(A) stack = [] res = 0 for i, a in enumerate(A): if not stack or stack[-1][1] > a: stack.append((i, a)) else: x = len(stack) - 1 while x >= 0 and stack[x][1] <= a: res = max(res, i - stack[x][0]) x -= 1 return res
-
func maxWidthRamp(nums []int) int { n := len(nums) stk := []int{} for i, v := range nums { if len(stk) == 0 || nums[stk[len(stk)-1]] > v { stk = append(stk, i) } } ans := 0 for i := n - 1; i >= 0; i-- { for len(stk) > 0 && nums[stk[len(stk)-1]] <= nums[i] { ans = max(ans, i-stk[len(stk)-1]) stk = stk[:len(stk)-1] } if len(stk) == 0 { break } } return ans } func max(a, b int) int { if a > b { return a } return b }