503. 下一个更大元素 II

题目

503. 下一个更大元素 II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

题解

首先是最朴素的思想，直接双层循环

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        L = [-9999]*n
        if n==0:
            return []
        for i in range(-1, n):
            L[i]=-1
            for j in range(i+1, i+n+1):
                j = j % n
                if nums[j] > nums[i]:
                    L[i] = nums[j]
                    break
        return L

但速度感人，时间复杂度为

执行用时：9264 ms, 在所有 Python 提交中击败了5.00%的用户
内存消耗：14.7 MB, 在所有 Python 提交中击败了83.50%的用户

优化1

我们在寻找更大数字时，是将 nums[i] 与 nums[j] 做比较，此时有两种情况

1. nums[i]<nums[j] ，这时可以直接让 L[i]=nums[j]
2. nums[i]>=nums[j]，这时我们将 nums[i] 与 L[j] 再进行一次比较，若 L[j]>nums[i] ，那么 L[j] 一定是 nums[i] 的下一更大元

   class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        L = [-9999]*n
        for i in range(n-2, -2, -1):
            L[i]=-1
            for j in range(i+1, i+n+1):
                j = j % n
                if nums[i] < nums[j]:
                    L[i] = nums[j]
                    break
                elif nums[i] < L[j]:
                    L[i] = L[j]
                    break
        return L
   

   这次执行用时 420 ms，速度快了20倍，但还是处于最后13%，一定还有可继续优化的地方。

优化2

在上面的基础上进一步优化：即使 L[j]<=nums[i]，我们也可以将 j 跳到 L[j] 对应的下标处。
这次执行用时 240 ms，但还是处于最后25%

class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        nums=nums*2
        L = [-99999999]*n
        idx = list(range(1,n+1))
        if n == 0:
            return []
        if n==1:
            return [-1]
        for i in range(n-1, -1, -1):
            L[i] = -1
            j = i+1
            while j < i+n+1:
                k = j % n
                if nums[i] < nums[k]:
                    L[i] = nums[k]
                    idx[i] = k
                    break
                elif nums[i] < L[k]:
                    L[i] = L[k]
                    idx[i] = idx[k]
                    break
                else:
                    j += (idx[k]-k+n) % n
        return L

# 执行用时：240 ms, 在所有 Python 提交中击败了25.00%的用户
# 内存消耗：15 MB, 在所有 Python 提交中击败了33.00%的用户

即使进行了两次优化，但在对于最坏的情况：序列严格单调递减，时间复杂度仍为

标准答案

这用到了一个叫做 单调栈 的结构，栈中储存的是数组的下标，我们维护这个栈，使得栈底到栈顶的下标所对应的元素非增。通过这个方法，我们只需将数组遍历一遍即可：

1. 对于当前下标 i
2. 我们将栈中对于元素小于 nums[i] 的全部出栈
3. 出栈下标所对应的更大值即为 nums[i]
4. 将 i 入栈

可以参看这个可视化过程： 代码可视化

class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        nums = 2*nums
        m_stack = []
        idx = [-1]*2*n
        for i in range(2*n):
            while m_stack != [] and nums[m_stack[-1]] < nums[i]:
                idx[m_stack.pop()] = nums[i]
            m_stack.append(i)
        return idx[:n]

最后的用时如下：

执行用时：184 ms, 在所有 Python 提交中击败了84.00%的用户 内存消耗：15.1 MB, 在所有 Python 提交中击败了21.50%的用户

其实也没快多少。。。
我的代码中应对循环的措施是将数组复制一倍，但是实际上并不需要，只需用将 i 模 n 即可，但测试后发现速度还慢一些。。。