new_contents: # Time:  O(n)
  # Space: O(n)
  
  # 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.
  
  class Solution(object):
      def nextGreaterElements(self, nums):
          """
          :type nums: List[int]
          :rtype: List[int]
          """
          result, stk = [0] * len(nums), []
          for i in reversed(xrange(2*len(nums))):
              while stk and stk[-1] <= nums[i % len(nums)]:
                  stk.pop()
              result[i % len(nums)] = stk[-1] if stk else -1
              stk.append(nums[i % len(nums)])
          return result
  
subject: Create next-greater-element-ii.py