难度: 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里面
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
lookup = collections.defaultdict(list)
for idx, num in enumerate(A):
lookup[num].append(idx)
unique_nums = sorted(lookup.keys()) # A中所有unique的数字列表
pool = []
for num in unique_nums:
heapq.heappush(pool, min(lookup[num]))
seen = set()
res = -sys.maxsize
for i in range(len(unique_nums) - 1, -1, -1):
while pool[0] in seen:
heapq.heappop(pool)
res = max(res, max(lookup[unique_nums[i]])-pool[0])
for j in lookup[unique_nums[i]]:
seen.add(j)
return res思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
参考寒神, beats 99.65%
Thinking of QYFeng in comments:
My thinking: this solution is truly ingenious. It exemplifies the author's keen observation and strong modelling and problem-solving skills. What is more remarkable is that the author constantly gives concise and beautiful solutions with high efficiency, that ordinary people cannot even imagine possible.
stack s contains the indices of the elements. The indices stored in s are increasing, while the elements corresponding to these indices are decreasing. It is guaranteed to include A[0], as well as the minimum of A.
In the second for loop, the indices are looped in decreasing order. Whenever an element corresponding to a s stack entry is no larger than A[j], it is popped and the differences in indices are calculated. Since j is the largest index with A[j] >= this element (hence j - s[-1] being the largest), popping it wouldn't cause any problems.
Q: What if some elements not included in s gives the maximum width ramp, and is the smaller element in the ramp?
A: It is impossible. Because an element not included in s will be larger than or equal to some elements in s, which appear earlier in A. Those smaller and earlier elements stored in s will give rise to a bigger width. On the other hand, it is certain that some elements not included in s is the larger element in max-width ramp.
Q: Why using a stack with decreasing element?
A: The stack s will only be popped if the last (smallest in A) element is no larger than A[j], which is guaranteed to be the max-width ramp (if it is a ramp at all, since j might be smaller than s[-1]) among the ramps with A[s[-1]] being the smaller element. Removing it would reduce the workload and not cause harm. The earlier an element is in s, the less likely that A[j] >= A[the element], so the stack must be popped from the tail to head.
Q: What is the key in this solution?
A: Constructing a stack and popping it gradually. Popping the stack guarantees that the second for loop has a Time Complexity of O(N), escaping the quadratic time complexity a brute-force algorithm will lead to.
Q: Overall, what is the intuition leading to this solution?
A: A max-width ramp should have its smaller element appear as "early" in A and as small as possible. All elements larger than A[0] are not possible to be the smaller element in the max-width ramp, hence they shouldn't be considered as the candidate smaller element; the same applies to arbitrary A'[0], where A' is a sublist A[i:] in which A[i] < A[0]; constructing a stack of candidate smaller elements in max-width ramp, which includes A[0] and all later and smaller elements, becomes natural. Otherwise, we must consider those uninteresting elements as candidate smaller element in max-width ramp and compare them, wasting a great deal of time.
class Solution(object):
def maxWidthRamp(self, A):
"""
:type A: List[int]
:rtype: int
"""
stack, res = [], 0
for i, num in enumerate(A):
if not stack or num < A[stack[-1]]:
stack.append(i)
for j in range(len(A))[::-1]:
while stack and A[j] >= A[stack[-1]]: # 注意这里用while的含义
res = max(res, j - stack.pop())
return res