The fundamental secret of Monotonic Stacks:

The stack always stores the "unresolved" problems, and we pop when we find the element that "resolves" them.

In every stack problem, you just have to identify "What is the event that stops the waiting game?"

If the event is "finding a bigger number," you keep a decreasing stack.

If the event is "finding a smaller number," you keep an increasing stack.

There is a spiritual link I feel here between monotonic stack problems and the optimal Longest Increasing Subsequence solution. That "spirit" I'm detecting is the concept of maintaining a candidate frontier.

Both the Monotonic Stack and the LIS (Patience Sorting/Tails) algorithms belong to a specific family of greedy algorithms that work by discarding suboptimal possibilities to maintain a sorted invariant.

The Core Philosophy: "Survival of the Fittest"

Both algorithms rely on the fact that if the data structure isn't sorted, we are holding onto redundant information.

The Difference: Replacement vs. Resolution

This is where they diverge, and why they solve different problems. It comes down to what you do when we break the sort order.

Scenario: The structure contains [... 10] and the new number is 5.
The LIS Approach (Replacement):
5 is better than 10 for that position.
Action: Overwrite. [... 10] becomes [... 5].
Meaning: "I found a better way to reach this state."

Scenario: The structure contains [... 5] and the new number is 10.
The Mono Stack Approach (Resolution):
10 solves the problem for 5.
Action: Pop 5.
Meaning: "The 5 is done. It found what it was looking for. Now let's see if 10 solves the guy behind 5."

We can think of both algorithms as maintaining a Pareto Frontier of valid states.

They both iterate and greedily maintain a sorted structure of "active candidates" and discarding anything that is no longer useful.

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        # Dictionary to store the next greater element for each number in nums2
        next_greater_map = {}
        stack = []
        
        # Iterate through nums2 to build the map
        for num in nums2:
            # While stack is not empty and current number is greater than stack top
            while stack and num > stack[-1]:
                val = stack.pop()
                next_greater_map[val] = num
            stack.append(num)
        
        # Iterate through nums1 to build the result
        # If the number exists in map, use the value. Otherwise -1.
        res = []
        for num in nums1:
            if num in next_greater_map:
                res.append(next_greater_map[num])
            else:
                res.append(-1)
                
        return res