962 Maximum Width Ramp

962. Maximum Width Ramp

1. Question

Given an arrayAof integers, aramp is a tuple(i, j)for whichi < j and A[i] <= A[j]. The width of such a ramp isj - i.

Find the maximum width of a ramp inA. 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

2. Implementation

(1) Stack

思路: 这道题要我们对于每个数A[j]，从左边找到一个数A[i]小于等于A[j]，其中i <= j, 找出(j - i)的最大差值。因为对于每个数，我们要往前找出一个小于等于它自己的数, 所以我们通过stack建立一个单调递减stack，这样stack.top()的数保证是小于等于当前的数。

• 所以第一步是扫一遍输入数组，建立单调递减stack，将符合条件的数的index放在stack中

• 第二步从后往前再扫一遍数组，如果stack.top()的数小于等于当前的数，则我们算出结果，并更新res的最大值

class Solution {
    public int maxWidthRamp(int[] A) {
        Stack<Integer> stack = new Stack();

        for (int i = 0; i < A.length; i++) {
           if (stack.isEmpty() || A[stack.peek()] > A[i]) {
               stack.push(i);
           }
        }

        int res = 0;
        for (int i = A.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && A[stack.peek()] <= A[i]) {
                res = Math.max(res, i - stack.pop());
            }
        }
        return res;
    }
}

3. Time & Space Complexity

Stack: Time: O(n), Space: O(n)