962. Maximum Width Ramp

962. Maximum Width Ramp

难度: Medium

刷题内容

原题连接

内容描述

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 <= 50000
0 <= A[i] <= 50000

解题方案

思路 1
- 时间复杂度: O(NlgN)- 空间复杂度: O(N)

我们先看一下A是否为严格单调递减列表,如果是就return 0

然后我们将A中所有数字作为key,他们出现的index的列表作为value存起来

从所有unique数字中的最大的数开始遍历,大的数字肯定要取他出现的最大的那个index,然后搞一个pool放比当前数字小的数字的出现的最小index,
另外维护一个seen字典,如果要取当前这个最大的数字作为最后结果,那么我们要取一个比它小的数字的出现的最小的那个index作为结果中的i,
记得每次把当前数字的所有出现的index放到seen里面

```python
class Solution(object):
def maxWidthRamp(self, A):
"""
:type A: List[int]
:rtype: int
"""
if all(A[i] < A[i-1] for i in range(1, len(A))):
return 0

top Created with Sketch.