Suppose we have a decreasing sequence followed by a greater number. For example [5, 4, 3, 2, 1, 6] then the greater number 6 is the next greater element for all previous numbers in the sequence. We use a stack to keep a decreasing sub-sequence, whenever we see a number x greater than stack.peek() we pop all elements less than x and for all the popped ones, their next greater element is x. For example [9, 8, 7, 3, 2, 1, 6]. The stack will first contain [9, 8, 7, 3, 2, 1] and then we see 6 which is greater than 1 so we pop 1 2 3 whose next greater element should be 6.
通过栈找出nums中每一个数字的后一个大的，通过map保存下来
Findnums中的数字如果没有在map中找到，则没有之后比其大的，则返回-1；如果找到了，返回map的value值
x in mapx是否在map的键值中
class Solution(object): def nextGreaterElement(self, findNums, nums): cache ={} stack=[] for x in nums: if len(stack) == 0: stack.append(x) elif x <= stack[-1]: stack.append(x) else: while stack and x >stack[-1]: cache[stack.pop()] = x stack.append(x) result = [] for x in findNums: if x in cache: result.append(cache[x]) else: result.append(-1) return result 一种比较笨的方法 class Solution(object): def __init__(self): self.nums = [] self.findNums = [] self.List=[] def nextGreaterElement(self, findNums, nums): """ :type findNums: List[int] :type nums: List[int] :rtype: List[int] """ # List=[] self.nums = nums self.findNums = findNums for i in range(len(self.findNums)): j = self.findPosition(self.findNums[i]) self.List.append(self.findBigger(self.findNums[i],j)) return self.List def findPosition(self,num_temp): for j in range(len(self.nums)): if self.nums[j] == num_temp: return j; def findBigger(self,num_temp,k): for i in range(k,len(self.nums)): if self.nums[i] > num_temp: return self.nums[i] return -1