<p>You are given the <code>head</code> of a linked list.</p>

<p>Remove every node which has a node with a greater value anywhere to the right side of it.</p>

<p>Return <em>the </em><code>head</code><em> of the modified linked list.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/02/drawio.png" style="width: 631px; height: 51px;" />
<pre>
<strong>Input:</strong> head = [5,2,13,3,8]
<strong>Output:</strong> [13,8]
<strong>Explanation:</strong> The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> head = [1,1,1,1]
<strong>Output:</strong> [1,1,1,1]
<strong>Explanation:</strong> Every node has value 1, so no nodes are removed.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of the nodes in the given list is in the range <code>[1, 10<sup>5</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
</ul>

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
#Reverse Twice
    #     def reverseList(node):
    #         prev,cur = None,node
    #         while cur:
    #             temp_nxt = cur.next
    #             cur.next = prev
    #             prev = cur
    #             cur = temp_nxt
    #         return prev
    #     #Reverse the first time
    #     new_head = reverseList(head)
    # #Delete any node smaller than the current node
    #     # prev = new_head
    #     # cur = prev.next
    #     # while cur:
    #     #     while cur and cur.val < prev.val:
    #     #         cur = cur.next
    #     #     prev.next = cur
    #     #     prev = cur
    #     #     if prev:
    #     #         cur = prev.next
    # #Or Maintain a cur_max variable to keep track of the max value encountered
    #     cur = new_head
    #     cur_max = cur.val
    #     while cur.next:
    #         if cur.next.val < cur_max:
    #             cur.next = cur.next.next
    #         else:
    #             cur_max = cur.next.val
    #             cur = cur.next
    #     #Reverse the second time
    #     new_head2 = reverseList(new_head)
    #     return new_head2
    #Time:O(n) Space:O(1)


#Monotonic Stack
        # stack  = []
        # while head:
        #     while stack and head.val > stack[-1]:
        #         stack.pop()
        #     stack.append(head.val)
        #     head = head.next
        # dummy = ListNode(0)
        # cur = dummy
        # for i in stack:
        #     cur.next = ListNode(i)
        #     cur = cur.next
        # return dummy.next
    #Time:O(n) Space:O(n)


# Recursion
        if not head or not head.next:
            return head
        head.next = self.removeNodes(head.next)
        if head.next and head.val < head.next.val:
            return head.next
        else:
            return head

# First Intuition
        # dummy = ListNode(0,head)
        # temp = dummy
        # prev,cur = head,head
        # while prev:
        #     while cur and cur.val <= prev.val:
        #         cur = cur.next
        #     if cur:
        #         prev = cur
        #         temp.next = cur
        #     else:
        #         temp = prev
        #         prev = prev.next
        #         cur = prev
        # return dummy.next
#Time:O(n^2) Space:O(1) Time Limit Exceeded
59891