# 962 Maximum Width Ramp

## 962. [Maximum Width Ramp](https://leetcode.com/problems/maximum-width-ramp/)

## 1. Question

Given an array`A`of integers, &#x61;_&#x72;amp_ 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`

## 2. Implementation

**(1) Stack**

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

* 所以第一步是扫一遍输入数组，建立单调递减stack，将符合条件的数的index放在stack中
* 第二步从后往前再扫一遍数组，如果stack.top()的数小于等于当前的数，则我们算出结果，并更新res的最大值

```java
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)
