This is summary of question under ** Monotonic stack tag**

1. Next greater / lesser problem , Previous greater / lesser problem:

When we try to find previous lesser element to current element, the monotonic increasing stack is needed. So we need to pop up top element in stack when top element is larger than current value. What is interesting is that current element is also the next lesser element of popped up value:

'''
As a new item gets added to the stack, older items are removed from the top if they are bigger. In other words, the items that are getting popped must be greater than or equal to the incoming element. We can also say that the incoming element must be the next smaller element of the item going off the stack. So, every time an item is popped, we get to know about its next smaller item.
'''

Because stack is increasing, it can only be like [1, 2, 7, 9] current is 4. So 4 must be next lesser element of item 7 and 9.

A comprehensive guide and template for monotonic stack based problems has really nice summary of fundamental monotonic stack algorithm for Next greater/lesser element or Previous greater/lesser element questions

1475. Final Prices With a Special Discount in a Shop
496. Next Greater Element I
Buildings With an Ocean View
739. Daily Temperatures
901. Online Stock Span
503. Next Greater Element II
1019. Next Greater Node In Linked List
1063. Number of Valid Subarrays

2. Construct binary tree from given array
Basic idea is that current node is the right node of previous larger node, if there is no previous larger node, then last popped out smaller node is the left node of current node.
654. Maximum Binary Tree
1008. Construct Binary Search Tree from Preorder Traversal
255. Verify Preorder Sequence in Binary Search Tree

3. Subsequece problem
This type of question normally ask to get lexicographically smallest / number smallest subsequence. Idea is to try to get least first element as possible. Also need to make sure condition is met.

The conditions for deletion are:
The character is greater than the current characters
The character can be removed because it occurs later on

We do ignore item which is already in stack and also delete occurence of this item by 1. when we pop up element, we also need to delete occurence of popped-out element by 1

for item in s:
	if item in stack:
		count[item] -=1
		continue
	while stack and stack[-1]>item and count[stack[-1]] >1:
		top = stack.pop()
		count[top] -=1
	stack.append(item)

316. Remove Duplicate Letters
1081. Smallest Subsequence of Distinct Characters
1673. Find the Most Competitive Subsequence
402. Remove K Digits

4. Count how many element between current item and next greater / lesser element(previous greater/ lesser element)
When we try to pop up element within while loop, we can start count number of items being popped out

2282. Number of People That Can Be Seen in a Grid

5. Subarray problem

Every subarry with length 1, 2, 3 ..n. Find either max, min or sum or substract

Get the number of subarrays that contain a specific element in a given range

As a new item gets added to the stack, older items are removed from the top if they are bigger. In other words, the items that are getting popped must be greater than or equal to the incoming element. We can also say that the current element must be the next smaller element of the item going off the stack. So, every time an item is popped, we get to know about its next smaller item

Edge Case - Duplicate Elements

One thing that we need to be careful about - we should make sure that we don't count the contribution by an element twice. This is possible in the cases such as [2, 2, 2]. While finding the boundary elements for a range, we look for elements that are strictly less than the current element on the left. To decide the right boundary, we look for the elements which are less than or equal to the current element.

This code is to get all larger elements 
stack = []
for idx in range(len(arr)):
	value = arr[idx]
	while stack and arr[stack[-1]] >= value:
		# for topped up element, previous element of it in stack is previous lesser value, arr[idx] is next lesser value
		top = stack.pop()
		right = idx - top
		if stack:
			left = top - stack[-1]
		else:
			left = top +1# all values prior it are larger 
		total += arr[top] * left * right
	stack.append(idx)

# In case that a few values left in stack, we need to pop them out manually
while stack:
	top = stack.pop()
	right = len(arr) - top
	if stack:
		left = top - stack[-1]
	else:
		left = top+1
	total += arr[top] * left * right

Same case for finding subarrays with value as maximum
2104. Sum of Subarray Ranges
907. Sum of Subarray Minimums
1856. Maximum Subarray Min-Product
Maximum of Minimum Values in All Subarrays

6. monotonic queue together with binary search
Given unsorted order list, find leftmost value which is smaller than current value:
This type of question requires decreasing monotonic stack and also binary search.
e.g. [6,0,8,2,1,5]
brutal force will do always find leftmost lesser element compared to current element. You can find that for 2, 1, 5, the first lesser element is 0. If we maintain a decreasing stack which is [6, 0]. It is leftmost elements for rest of all elements.

        result = 0
        for end in range(len(nums)):
            for start in range(end):
                if nums[start] <= nums[end]:
                    result = max(result, end-start)
                    break
        return result

So we can loop through list and construct a decreasing monotonic stack by checking wether last element in stack is greater than incoming element. If yes, then append it to stack otherwise ignore it.

        stack = []
        for idx, item in enumerate(nums):
            if not stack or nums[stack[-1]]>item:
                stack.append(idx)

Then for each element in list, we can use binary search to find index of first lesser element in stack.

 for idx, item in enumerate(nums):
            start = 0
            end = len(stack)-1
            while start <= end:
                mid = (start + end)//2
                if nums[stack[mid]] <= item:
                    end = mid - 1
                else:
                    start = mid+1
            result = max(result, idx - stack[start])

962. Maximum Width Ramp

7. Monotonic stack but manily compare current with top of stack then determine whether add or not current
853. Car Fleet
2345. Finding the Number of Visible Mountains

8. 132 pattern
The reason why i take this question out because it requires deep understand of monotonic stack when element is popped up
456. 132 Pattern

the key to solve this question is to

• First, get minimum value to each position by iterating the array

• Second, traversing array from back to maintain a decreasing monotonic stack. Why ? because when we try to maintain a decreasing monotonic stack, we need to pop up element on top of stack when top value is smaller than current value. This gives us all smaller value to the right of current element.

• Third, compare popped smaller element with global minimum value given current postion from left

The bad part is that if questions requires that return all 132 pattern subsequence. This way can not make it because it breaks some 132 pattern for later postion.

Thinking case : [8, 10, 0, 100, 9, 1000]. Algorithm can return True when we traverse idx 3 from back, but we pop 9 out because we need to maintain a decrease order. This causes idx 1 (value 10) lose the right max smaller value 9.

So this code can only be used for this question. It can not be reused to any other question which not returns boolen.

This question is quite tricky and i personally feel that if you encounter this quesiton in interview, it is likely that your interviewer does not want you to pass it tbh

9. Greedy(I personally hate these category as it is like brain teaser)
1996. The Number of Weak Characters in the Game

10. Sort subarry / remove subarry in order to make whole array ascending
581. Shortest Unsorted Continuous Subarray
769. Max Chunks To Make Sorted