Q503 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.

解题思路：

题意为：给一个循环列表（最后一个元素与第一个元素相同），求出列表中每个元素的下一个较大的元素是什么（最大值没有下一个较大的元素，对应位置为-1）。

以 nums = [100,9,1,11,1,120,111,123,1,-1,-100,103,98,100] 为例，我们可以观察到几个性质：

• 在最大值（123）左侧，如果前面的数比后面的数小，则把后面的数当做较大值（如 9 < 11）；
• 在最大值（123）右侧，如果一直到列表结束都找不到较大的数（如103），则需要重新再遍历一次列表，找到下一个较大的数（120）。

1. 思路一：

• 设置两个指针 i 和 j，i 始终指向当前元素。然后，将 nums 扩宽 2 倍，j 每次指向下一个较大的元素。当 i 的指针达到原 nums 的长度，则退出循环。注意，当 i 指向 103，j 向后找到 120，然后，j 还要回退到 i 的下一个位置，不然，98就找不到下一个较大的数 100。这种情况下，最坏时间复杂度为 O(n^2)，Python3 版本会超时（C++ 和 Java不会）。

2. 思路二：

• 使用一个栈，遍历列表，栈中存放还未确定下一个较大元素的下标，如果遇到一个较大的数，则进入一个新的循环，把未确定的元素出栈，直到栈中留下的元素比当前的元素大。（比如，[100,9,1] 都先放入栈中，因为它们都还未找到较大的元素，下一次，遇到 11，则 1 比 11 小，1 出栈；此时继续循环判断栈中的 9, 9 也比 11 小，9 出栈；100 比 11 大，则栈中元素不能在确定下一个较大的元素了，则 11 入栈，继续遍历列表）。
• 当一次遍历结束后，只有 [123,103,100] 还在栈中。这时，只需要重新再次遍历一遍列表，100 比 120 小，出栈；103 比 120 小，出栈；直到再次遇到最大数123，则循环结束。
• 因为不涉及指针回退，则时间复杂度 O(n)，但空间复杂度 O(n)

Python 实现：

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]