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-CommentsA = [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
// Stack is often used for problems like
// find nearest larger/smaller elem (like water container problem)
// here it's to find furthest larger/smaller elem (a bit harder than water container problme)
// Time=O(N) Space=O(N)
public int maxWidthRamp(int[] A) {
// scanning from left to right to get all possible indices of the min element seen so far
// think a bit and you'll discover they are valid START INDICES candidates for the widest ramp
// they are [i0, i1, i2, i3, i4] as in the pic attached, you could use the pic to think on the algorithm
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);
}
}
// now scanning backwards for all other non-min elements, let them pair with all the candidates
// we've collected in the first step in stack. Meanwhile, if we've discover that the current index i could
// form a ramp with a min idx j, we know j couldn't form a better solution since i is going backwards
// so we pop j out of stack
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;
}
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;
}
Improve the idea above.
Still one pass and keep a decraesing stack.
Still one pass and keep a decraesing stack.
based on my understanding, the problem is :
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.
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.
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;
}
这里用到的是单调递减栈，如果遇到一个数字，比栈顶元素更小，那么就入栈；否则就在栈里边向后找到第一个刚好小于等于它的元素，此时的距离就是最远距离。
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
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,
https://leetcode.com/problems/maximum-width-ramp/discuss/208341/O(N)-JAVAleft 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 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;
}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;
}
// 1. sort on value
// 2. sort on index <-- used in this problem Time=O(NlgN), Space=O(N)
public int maxWidthRamp2(int[] A) {
// sort index according to values and then do a dp
int N = A.length;
Integer[] indices = new Integer[N]; // need to use Integer for Arrays.sort with lambda to work
Arrays.setAll(indices, i -> i);
Arrays.sort(indices, (i, j) -> A[i] != A[j] ? A[i] - A[j] : i - j);
// use dp to find min idx so far
int minIdx = indices[0];
int res = 0;
for (int idx : indices) {
res = Math.max(res, idx - minIdx);
minIdx = Math.min(minIdx, idx);
}
return res;
}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.
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;
}
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
This 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;
} 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;
} //------ Solution 1 Brute force -------------//
// brute force with fast break
// Time=O(N^2) (a bit better) Space=O(1)
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; // stop inner loop at the first valid index j
}
}
}
return res;
}这种思路的最差时间复杂度是O(n^2)，最优时间复杂度是O(1)，空间复杂度是O(1)。
https://leetcode.com/problems/maximum-width-ramp/discuss/211756/Normal-DP-%2B-pruning-solution-in-Javapublic 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;}
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;
}