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 <= 500000 <= A[i] <= 50000
X.
https://zxi.mytechroad.com/blog/stack/leetcode-962-maximum-width-ramp/
- Using a stack to store start candidates’ (decreasing order) index
- Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.
e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END
https://leetcode.com/problems/maximum-width-ramp/discuss/210812/3-Java-Solutions-1)-Brute-Force-2)-Sort-3)-Stack-with-Detailed-Comments
public int maxWidthRamp(int[] A) {
int N = A.length;
Stack<Integer> s = new Stack();
for (int i = 0; i < N; i++) {
if (s.isEmpty() || A[i] < A[s.peek()]) {
s.push(i);
}
}
int res = 0;
for (int i = N - 1; i >= 0; i--) {
while (!s.isEmpty() && A[s.peek()] <= A[i]) {
res = Math.max(res, i - s.pop());
}
}
return res;
}
https://leetcode.com/problems/maximum-width-ramp/discuss/208331/C%2B%2B-5-lines-search-in-decreasing-stack-O(n-log-n)
You may wonder why are we checking elements left to right while the maximum is likely to be on the far right side? If we check elements right to left, we do not need to keep smaller elements in the stack. So, we first populate the stack left to right with elements in decreasing order, and then go right to left and pop all elements smaller than the current one. This gives us O(n) runtime. One additional optimization is to populate stack until the top <= A[A.size() - 1].
int maxWidthRamp(vector<int>& A, int res = 0) {
vector<int> v = { 0 };
for (int i = 1; A[v.back()] > A[A.size() - 1]; ++i)
if (A[v.back()] > A[i]) v.push_back(i);
for (int j = A.size() - 1; j > res; --j)
while (!v.empty() && A[v.back()] <= A[j]) {
res = max(res, j - v.back());
v.pop_back();
}
return res;
}
https://leetcode.com/problems/maximum-width-ramp/discuss/208348/JavaC%2B%2BPython-O(N)-Using-Stack
Improve the idea above.
Still one pass and keep a decraesing stack.
based on my understanding, the problem is :
for each element A[i], we need to go back left to find the farthest element that is smaller than A[i].
I do spent a while to figure out why we need to pop() when we have while (!s.empty() && A[s.top()] <= A[i]), then I realize, if A[s.top()] <= A[i] A[s.top()], since we keep a descending order stack , so we also have A[s.top()] <= A[i - 1], and since A[i] - s.top() > A[i - 1] - s.top(), so we need to pop to avoid duplicated calculation.
Then people may ask why descending order stack? because for each element we need to look back for a smaller or equal value, and a descending order stack can guarantee that the top element is always smaller or equal to current element.
The stack is used to store all candidate start points.
And by comparing elements (starting from the end of the array) with those candidates, we can eliminate points that are not bigger than the candidate.
Time Complexity:
O(N)
public int maxWidthRamp(int[] A) {
Stack<Integer> s = new Stack<>();
int res = 0, n = A.length;
for (int i = 0; i < n; ++i)
if (s.empty() || A[s.peek()] > A[i])
s.add(i);
for (int i = n - 1; i > res; --i)
while (!s.empty() && A[s.peek()] <= A[i])
res = Math.max(res, i - s.pop());
return res;
}
Keep a decraesing stack.
For each number,
binary search the first smaller number in the stack.
When the number is smaller the the last,
push it into the stack.
Time Complexity:
O(NlogN)
public int maxWidthRamp(int[] A) {
List<Integer> s = new ArrayList<>();
int res = 0, n = A.length;
for (int i = 0; i < n; ++i) {
if (s.size() == 0 || A[i] < A[s.get(s.size() - 1)]) {
s.add(i);
} else {
int left = 0, right = s.size() - 1, mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (A[s.get(mid)] > A[i]) {
left = mid + 1;
} else {
right = mid;
}
}
res = Math.max(res, i - s.get(left));
}
}
return res;
}
X.
https://blog.csdn.net/fuxuemingzhu/article/details/85223568
这里用到的是单调递减栈，如果遇到一个数字，比栈顶元素更小，那么就入栈；否则就在栈里边向后找到第一个刚好小于等于它的元素，此时的距离就是最远距离。
Not efficent
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
X. Left + right array
https://www.acwing.com/solution/LeetCode/content/672/
1. 维护一个前缀最小值数组 minlminl，和一个后缀最大值数组 maxrmaxr。例如，[6,0,8,2,1,5] 的两个数组分别为 [6,0,0,0,0,0], [8,8,8,5,5,5]。
2. 定义两个指针，初始时分别指向两个数组的开头，如果 minl[i] <= maxr[j]，则更新答案后 j；否则 i；
3. 解释：如果 minl[i] <= maxr[j]，则说明在 i 之前（包括 i）必定有一个数字小于等于 j之后（包括 j）的某个数字。且左端的数字就是 A[i]，因为 i 是从最小的开始往后走的，故此时只需要向后移动 j，去尝试 j之后的数字某个是否也可行。
4. 如果 minl[i] > maxr[j]，则说明 i 之前（包括 i）的所有数字都比 j 之后（包括 j）的所有数字要大，所以 i 需要向后移动寻找一个小一些的数字。
https://leetcode.com/problems/maximum-width-ramp/discuss/209582/O(n)-time-O(n)-space-using-two-array
Use two array to solve this problem. min_arr[i] is the minimum of the first i + 1 elements of A, max_arr[j] is the maximum of the last len(A) - j elements of A.
The idea of this solution is: Suppose (i, j) is the answer, then A[i] must be the smallest element among the first i + 1 elements of A and A[j] must be the largeset element among the last len(A) - j elements of A. Otherwise, we can always find an element smaller than A[i] or larger than A[j], so that (i, j) is not the maximum width ramp.
For example, the input is [6, 0, 8, 2, 1, 5]. Then min_arr=[6, 0, 0, 0, 0, 0] and max_arr=[8, 8, 8, 5, 5, 5].
We can find the ramp use two points, left and right. left starts from the beginning of min_arr[i] and right starts from the beginning of max_arr[i]. Increase right by 1 when min_arr[left] <= max_arr[right], else increase left by 1
https://leetcode.com/problems/maximum-width-ramp/discuss/208341/O(N)-JAVA
public int maxWidthRamp(int[] A) {
int n = A.length;
int i, j , max = 0;
int[] maxR = new int[n], minL = new int[n];
minL[0] = A[0];
for (i = 1; i < n; i++){
minL[i] = Math.min(A[i], minL[i - 1]);
}
maxR[n - 1] = A[n - 1];
for (j = n - 2; j >= 0; j--){
maxR[j] = Math.max(A[j], maxR[j + 1]);
}
i = 0; j = 0;
while (i < n && j < n){
if (minL[i] <= maxR[j]){
max = Math.max(max, j - i);
j++;
}else{
i++;
}
}
return max;
}
You don't need to calculate minL, only maxR should work!
public int maxWidthRamp(int[] A) {
if(A.length == 0){
return 0;
}
int[] maxR = new int[A.length];
maxR[A.length-1] = A[A.length-1];
for(int i=A.length-2;i>=0;i--){
maxR[i] = Math.max(A[i], maxR[i+1]);
}
int i=0;
int j=0;
int res = 0;
while(i<A.length && j<A.length){
if(A[i]<=maxR[j]){
res = Math.max(res, j-i);
j++;
}else{
i++;
}
}
return res;
}
X. Two Pointers
https://leetcode.com/problems/maximum-width-ramp/discuss/208328/Two-pointer-O(nlogn)-C%2B%2B-O(n)-space
After i had stored the useful information from problem using vector of pair. I sorted the array.
After I used two pointer consecutive to each other ( pointer at begining and end is not feasible)
int maxWidthRamp(vector<int>& A)
{
vector<pair<int, int>> vec;
int n = A.size();
for (int i = 0; i < n; ++i) vec.push_back({A[i], i});
sort(vec.begin(), vec.end());
int i = 0, j = 1, res = 0;
while (j < n)
{
if (vec[i].second <= vec[j].second)
{
res = max(res, vec[j].second - vec[i].second);
++j;
}
else ++i;
}
return res;
}
public int maxWidthRamp(int[] A) {
int modA[][] = new int[A.length][2];
for (int i = 0 ; i < A.length ; i++) {
modA[i] = new int[] { A[i], i};
}
Arrays.sort(modA, (m1, m2) -> m1[0] - m2[0]);
int i = 0;
int j = 1;
int maxWidth = 0;
while (j < A.length) {
if (modA[j][1] > modA[i][1]) {
maxWidth = Integer.max(maxWidth, modA[j][1] - modA[i][1]);
j++;
}
else
i++;
if (i == j)
j++;
}
return maxWidth;
}
X.
https://leetcode.com/articles/maximum-width-ramp/
Approach 1: Sort
For all elements like A[i] = v, let's write the indices i in sorted order of their values v. For example with A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4, we can write the order of indices i=1, i=3, i=2, i=0.
Then, whenever we write an index i, we know there was a ramp of width i - min(indexes_previously_written) (if this quantity is positive). We can keep track of the minimum of all indexes previously written as m.
public int maxWidthRamp(int[] A) {
int N = A.length;
Integer[] B = new Integer[N];
for (int i = 0; i < N; ++i)
B[i] = i;
Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));
int ans = 0;
int m = N;
for (int i : B) {
ans = Math.max(ans, i - m);
m = Math.min(m, i);
}
return ans;
}
public int maxWidthRamp2(int[] A) {
int N = A.length;
Integer[] indices = new Integer[N];
Arrays.setAll(indices, i -> i);
Arrays.sort(indices, (i, j) -> A[i] != A[j] ? A[i] - A[j] : i - j);
int minIdx = indices[0];
int res = 0;
for (int idx : indices) {
res = Math.max(res, idx - minIdx);
minIdx = Math.min(minIdx, idx);
}
return res;
}
Approach 2: Binary Search Candidates
https://www.jianshu.com/p/cb458cc61e31
Keep a decresing stack.
For each number,
binary search the first smaller number in the stack.
When the number is smaller the the last,
push it into the stack.
def maxWidthRamp(self, A):
stack = []
res = 0
for i in range(len(A))[::-1]:
if not stack or A[i] > stack[-1][0]:
stack.append([A[i], i])
else:
j = stack[bisect.bisect(stack, [A[i], i])][1]
res = max(res, j - i)
return res
Consider i in decreasing order. We want to find the largest j with A[j] >= A[i] if it exists.
Thus, the candidates for j are decreasing: if there is j1 < j2 and A[j1] <= A[j2] then we strictly prefer j2.
Algorithm
Let's keep a list of these candidates j. For example, with A = [0,8,2,7,5], the candidates for i = 0 would be candidates = [(v=5, i=4), (v=7, i=3), (v=8, i=1)]. We keep the list of candidates in decreasing order of i and increasing order of v.
Now we can binary search to find the largest j with A[j] >= A[i]: it's the first one in this list of candidates with v >= A[i].
public int maxWidthRamp(int[] A) {
int N = A.length;
int ans = 0;
List<Point>
candidates =
new ArrayList();
candidates.add(new Point(A[N - 1], N - 1));
// candidates: i's decreasing, by increasing value of A[i]
for (int i = N - 2; i >= 0; --i) {
// Find largest j in candidates with A[j] >= A[i]
int lo = 0, hi = candidates.size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (candidates.get(mi).x < A[i])
lo = mi + 1;
else
hi = mi;
}
if (lo < candidates.size()) {
int j = candidates.get(lo).y;
ans = Math.max(ans, j - i);
} else {
candidates.add(new Point(A[i], i));
}
}
return ans;
}
X. TreeMap
https://jinx19.github.io/2018/12/23/LeetCode-Solution-2018-12-23-LeetCode-Solution-962-Maximum-Width-Ramp/
https://leetcode.com/problems/maximum-width-ramp/discuss/208659/Simple-java-solution-with-TreeMap
Th
is solution is similar to decending stack solution, but with TreeMap, we can further simplify the logic as treemap maintains the natural ordering, to search a particular value is more straight forward with method of: TreeMap.floorEntry().
The map stores the value to postion mapping. The values is sorted in ascending order.
public int maxWidthRamp(int[] A) {
int max = 0;
NavigableMap<Integer, Integer> valPosMap = new TreeMap<>();
for (int i = 0; i < A.length; i++) {
if (i == 0 || A[i] < valPosMap.firstKey())
valPosMap.put(A[i], i);
else {
int cur = i - valPosMap.floorEntry(A[i]).getValue();
if (cur > max)
max = cur;
}
}
return max;
}
https://leetcode.com/problems/maximum-width-ramp/discuss/209060/TreeMap-O(nlogn)-8-lines-of-Java
public int maxWidthRamp(int[] A) {
TreeMap<Integer, Integer> tm = new TreeMap<>();
int res = 0;
for (int i=A.length-1; i>=0; i
Integer k = tm.ceilingKey(A[i]);
if (k == null)
tm.put(A[i], i);
else
res = Integer.max(res, tm.get(k)-i);
}
return res;
}
X.
https://leetcode.com/problems/maximum-width-ramp/discuss/210812/3-Java-Solutions-1)-Brute-Force-2)-Sort-3)-Stack-with-Detailed-Comments
public int maxWidthRamp1(int[] A) {
int N = A.length;
int res = 0;
rightIdx: for(int i = 0; i < A.length; ++i) {
leftIdx: for(int j = 0; j < i; ++j) {
if (A[i] >= A[j]) {
res = Math.max(res, i - j);
continue rightIdx;
}
}
}
return res;
}
https://kingsfish.github.io/2018/12/23/Leetcode-962-Maximum-Width-Ramp/
这种思路的最差时间复杂度是O(n^2)，最优时间复杂度是O(1)，空间复杂度是O(1)。
public int maxWidthRamp(int[] A) {
int n = A.length;
int max = 0;
for (int i = 0; i < n; i ++) {
if(max >= n - 1 - i){
break;
}
for (int j = n - 1; j > i; j --) {
if (A[j] >= A[i]) {
max = Math.max(max, j - i);
}
}
}
return max;
}
https://leetcode.com/problems/maximum-width-ramp/discuss/211756/Normal-DP-%2B-pruning-solution-in-Java
public int maxWidthRamp(int[] A) {
int[] dp = new int[A.length+1];
int res = 0;
for(int i = 2; i < A.length + 1; ++i){
int maxval = 0;
for(int j = 1; j < i; ++j) {
if(A[i-1] >= A[j-1]) {
maxval = Math.max(maxval, dp[j-1] + (i-j));
break;
}
}
res = Math.max(res, maxval);
}
return res;
}
