# 962. Maximum Width Ramp

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:

1. `2 <= A.length <= 50000`
2. `0 <= A[i] <= 50000`

``````class Solution {
public:
int maxWidthRamp(vector<int>& A) {
int n = A.size(), res = 0;
vector<int> idx;
for (int i = 0; i < n; ++i) {
if (idx.size() == 0 || A[i] < A[idx.back()]) {
idx.push_back(i);
} else {
int left = 0, right = (int)idx.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (A[idx[mid]] > A[i]) {
left = mid + 1;
} else {
right = mid;
}
}
res = max(res, i - idx[right]);
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/962

https://leetcode.com/problems/maximum-width-ramp/

https://leetcode.com/problems/maximum-width-ramp/discuss/208348/JavaC%2B%2BPython-O(N)-Using-Stack

https://leetcode.com/problems/maximum-width-ramp/discuss/265765/Detailed-Explaination-of-all-the-three-approaches

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation