题目如下：

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: 4Explanation: 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: 7Explanation: 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

解题思路：假设n为数组中的最大值，并且该数组的maximum width ramp由n作为起点，那么显然maximum width是数组中最后一个n的下标减去数组中第一个n的下标。如果数组的maximum width ramp由m作为起点，并且m是次大值，那么maximum width是数组中最后一个m与最后一个n中下标的较大值减去数组中第一个的下标。知道这个规律后题目就很简单了，首先遍历整个数组，找出所有元素第一次和最后一次出现的下标（如果元素只出现一个，这两个值相等）并且存入字典中，接下来按数组中元素从大到小开始遍历，每遍历一个元素，更新一次所有大于等于自身的元素中最右边的那个下标，与自身最左边的下标相减，即可得到以这个元素作为起点的width，最后求出最大值。

代码如下：

class Solution(object):    def maxWidthRamp(self, A):        """        :type A: List[int]        :rtype: int        """        dic = {}        uniq = []        for i,v in enumerate(A):            if v not in dic:                dic[v] = [i]                uniq.append(v)            elif len(dic[v]) == 1:                dic[v].append(i)            else:                dic[v][1] = i        uniq.sort(reverse=True)        right = None        res = 0        for i,v in enumerate(uniq):            if right == None:                right = dic[v][-1]            right = max(right, dic[v][-1])            res = max(res,right - dic[v][0])        return res