LeetCode Q.2454

[StarsExpress]

https://github.com/doocs/leetcode/blob/main/solution/2400-2499/2454.Next%20Greater%20Element%20IV/README.md

Your time complexity is O(nlogn).
Time complexity can achieve O(n) by double stacks.

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        total_nums = len(nums)
        second_next_greater = [-1] * total_nums

        # Decreasing monotonic stacks: (num, idx).
        stack_1, stack_2 = [(nums[0], 0)], []
        # Increasing monotonic list to transport tuples from stack 1 to stack 2.
        transporter = []

        for current_idx in range(1, total_nums):
            while stack_2 and stack_2[-1][0] < nums[current_idx]:
                _, past_idx = stack_2.pop(-1)
                second_next_greater[past_idx] = nums[current_idx]

            while stack_1 and stack_1[-1][0] < nums[current_idx]:
                transporter.append(stack_1.pop(-1))
            
            stack_2.extend(transporter[::-1])  # Ensure decreasing monotonicity.
            transporter.clear()
            stack_1.append((nums[current_idx], current_idx))

        return second_next_greater