下一个更大的数(二)

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/3923970e95b140fdb65e6c00bcda403d?tpId=196&tqId=40444&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        环形数组问题：
            先将数组展开，新数组看作是nums + nums[:-1]，新数组的长度变为0 ~ 2*n-2；当然我们也可以对n取模，这样就不需要分配空间了
        建立单调递减栈，栈中存储元素下标
        遍历新数组0 ~ 2n-2：
            若stack为空 或者 nums[i] < stack[-1]：
                下标i%n入栈
            否则：
                栈顶元素出栈
                res[stack[-1]] = nums[i]
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n), 单调栈的长度
    """

    def nextBigger(self, nums):
        # write code here
        n = len(nums)

        res, stack = [-1] * n, []
        for i in range(2 * n - 1):
            while stack and nums[stack[-1]] < nums[i % n]:
                idx = stack.pop()
                if res[idx] == -1:
                    res[idx] = nums[i % n]
            stack.append(i % n)
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums = [2, 3, 4, 1]

    nums = [4, 3, 2, 1]

    res = sol.nextBigger(nums)

    print res