Next Greater Element I

如果要保证O(n)的时间复杂度，这里自己只想出了利用栈和哈希表一起来查找的方法，栈用来找右边相邻的大数，哈希用来记录位置

class Solution(object):
    def nextGreaterElement(self, findNums, nums):
        """
        :type findNums: List[int]
        :type nums: List[int]
        :rtype: List[int]
        """
        store = {}
        stack = []
        for index, num in enumerate(nums):
            while stack and nums[stack[-1]] < num:
                store[nums[stack.pop()]] = num
            stack.append(index)

        while stack:
            store[nums[stack.pop()]] = -1

        result = []
        for num in findNums:
            result.append(store[num])
        return result

Next Greater Element II

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.

Example 1:

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.

这道题的思路很好想其实，我们每次只需要把比当前栈顶对应元素还要小的值压入栈中，而如果是比栈顶大，则把栈中的元素一直弹出并把他们对应位置的greater element改成当前元素即可，另外这里需要注意数组是肯定需要遍历两遍才行的，考虑[7,6,5,4,3,2,1]这个数组就知道了，第一遍遍历是不可能把所有元素的greater element赋值的，只有第二遍才行，另外最后我们还需要把栈清空，这么做的原因则考虑[7,7,7,6,5,4,3,2,1]，显然三个最大值7是没有greater element的，只能最后从栈中单独清理出来，下面是自己的代码，感觉比LeetCode的答案更加易于理解

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)

        if not n:
            return []

        res = [None] * n
        stack = [0]

        # 第一遍循环把数组中的部分数赋予了greater element（指在最大值出现之前的所有数）

        for i in xrange(1, n):
            if nums[stack[-1]] >= nums[i]:
                stack.append(i)
                continue
            while stack and nums[stack[-1]] < nums[i]:
                index = stack.pop()
                res[index] = nums[i]
            stack.append(i)

        # 第二遍循环将最大值之后的数赋予greater element

        for i in xrange(n):
            while stack and nums[stack[-1]] < nums[i]:
                index = stack.pop()
                res[index] = nums[i]

            if not stack:
                break

        # 第三遍清空栈将最大值或者和最大值相等的所有数赋予greater element

        while stack:
            res[stack.pop()] = -1

        return res

二刷简洁版

class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        stack = []
        n = len(nums)
        result = [0] * n
        for i in xrange(n):
            while stack and nums[stack[-1]] < nums[i]:
                result[stack.pop()] = nums[i]
            stack.append(i)

        for i in xrange(n):
            while stack and nums[stack[-1]] < nums[i]:
                result[stack.pop()] = nums[i]

        while stack:
            result[stack.pop()] = -1

        return result