Problem description:

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:

1
2
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:

1
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

Solution:

  • Brute force
    use two pointers to solve. One start from left, the other one start from right side of array. 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int maxWidthRamp(vector<int>& A) {
            //brute force
            
            int res= INT_MIN;
            for(int left= 0; left< A.size()-1; left++){
                for(int right= A.size()-1; right> left; right--){
                    if(A[right]>= A[left]){
                        res= max(res, right-left);
                    }
                }
            }
            return res == INT_MIN? 0: res;
        }
    };

time complexity: $O(n^2)$
space complexity: $O(1)$

  • Decreasing Stack
    Use a stack to keep small elements index start from the left.
    ex:
    [6,0,1,2], then the stack will have [0,1] (this is the index).
    A[0] is because the stack was empty.
    A[1] is smaller than A[0], so push into stack.
    Rest of the elements all greater than A[1], so no need to keep in stack.

The second step is to find the maximum ramp, which start traverse from the right side of the array. One thing to notice is that, we don’t need to keep finding if the remain distance is smaller than the maximum ramp we already have.
ex:
[6,0,8,2,1,5]

  1. [0,1] is the stack
  2. start from right side of the array. which is A[5]= 5
    5-1= 4, which is the current maximum ramp we have. Then pop out the element from the stack to see if we can find a maximum ramp if use current right as a pivot.
  3. This guarantee us to find a left index with smaller value.
  4. We don’t need to keep finding if we’ve already reach the longest distance we can have.
    in this case, res= 4, i= 4 so we don’t need to move the right pointer toward left anymore.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        //use a stack to keep a decreasing numbers
        stack<int> stk;
        for(int i= 0; i< A.size(); i++){
            if(stk.empty() || A[stk.top()] > A[i]){
                stk.push(i);
            } 
        }
        
        int res= 0;
        for(int i= A.size()-1; i> res; i--){
            while(!stk.empty() && A[stk.top()]<= A[i]){
                //printf("stk.top=%d, i= %d\n", stk.top(), i);
                res= max(res, i- stk.top());
                
                stk.pop();
            }
            //printf("i=%d ,res=%d\n", i, res);
        }
        return res;
        
    }
};

time complexity: $O(n)$
space complexity: $O(n)$

reference:
https://goo.gl/97BXKc