Python O(n) - Use Two Monotonic Stacks
Intuition\n Describe your first thoughts on how to solve this problem. \nIf the question asked next biggest element, an intuitive solution would be to use a mon
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf the question asked next biggest element, an intuitive solution would be to use a monotonic stack. But, the quesiton is asking the "second" biggest element, so it might be worthwhile to explore the use of a second stack. \n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst stack is used for things that haven\'t seen the next greater element yet. Once an element has seen the next biggest element, it is moved to the second stack. When we traverse the list, we first compare the new element against the second stack and pop things off and update the result array. Then, we compare against the first stack. For this, we also need to store the indices to know what index/element to update.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N) as each element is compared a constant number of times as we have two stacks. \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nclass Solution:\n    def secondGreaterElement(self, nums: List[int]) -> List[int]:\n        firstStack = []\n        secondStack = []\n        n = len(nums)\n        res = [-1] * n\n        for index, x in enumerate(nums):\n            acc = []\n            while secondStack and x > secondStack[-1][0]:\n                resX, resI = secondStack.pop()\n                res[resI] = x\n            while firstStack and x > firstStack[-1][0]:\n                acc.append(firstStack.pop())\n            for ac in acc[::-1]:\n                secondStack.append(ac)\n            firstStack.append((x, index))\n        return res\n\n```
['Monotonic Stack', 'Python3']