Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.
题意为:给一个循环列表(最后一个元素与第一个元素相同),求出列表中每个元素的下一个较大的元素是什么(最大值没有下一个较大的元素,对应位置为-1)。
以 nums = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100] 为例,我们可以观察到几个性质:
class Solution:
# 超时版本:最坏时间复杂度为 O(n^2)
def nextGreaterElements(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
lens = len(nums)
if lens == 0:
return []
maxnum = max(nums) # nums 中的最大值
nums = nums + nums # 将 nums 扩展成 2 倍长
ret = [] # 返回值
i = j = 0 # i 指向当前数,j 指向下一个较大数
while i < lens:
if nums[i] == maxnum: # 最大值位置直接为 -1
ret.append(-1)
i += 1; j += 1
elif nums[i] < nums[j]:
ret.append(nums[j])
i += 1; j = i + 1 # j 指针回退
else:
j += 1
return ret
# AC版本:最坏时间复杂度为 O(n),但空间复杂度也为 O(n)
def nextGreaterElements2(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
lens = len(nums)
if lens == 0:
return []
maxnum = max(nums) # nums 中的最大值
ret = [-1] * lens # 返回值
stack = [] # 存储还未确定的下一个较大数的元素
for i in range(lens):
while stack and nums[stack[-1]] < nums[i]:
ret[stack.pop()] = nums[i]
stack.append(i)
# print(stack)
for i in range(lens):
while stack and nums[stack[-1]] < nums[i]:
ret[stack.pop()] = nums[i]
if maxnum == nums[i]:
break
return ret
a = [3,1,4,2,5,3]
a = [3,5,4,2,5,1,3]
a = [3,1,5,4,6,5,2,6,5,4,3]
a = [6,5,3,1,4,5,6,7,6,5,4,3,2,6]
a = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100]
print(Solution().nextGreaterElements2(a))
# [120, 11, 11, 120, 120, 123, 123, -1, 103, 103, 103, 120, 100, 120]