# After solved 1000 medium leetcode found thes patterns — Mono-Stack

`index :  0  1  2  3  4  5  6  7Array : [3, 7, 1, 4, 7, 2, 9, 8] stack1: :index=0           [3,7]:index=1               :index=2                  [1,4]:index=3                     [1,4,7]:index=4                        [1,2]:index=5                           [1,2,9]:index=6                               [1,2,8]:index=7Array : [3, 7, 1, 4, 7, 2, 9, 8] stack2: :index=0            :index=1               [7,1]:index=2                  [7,4]:index=3                     [7,7]:index=4                        [7,7,2]:index=5                            :index=6                               [9,8]:index=7`
`stack = []for i in range(len(arr)): # loop from last to first                          # change to >= for increasing stack    while stack and stack[-1] <= arr[i]:         val = stack.pop()        if condition(val):            update_result(val)    stack.append(arr[i])`
`def nextGreaterElements(self, nums: List[int]) -> List[int]:    """          1 2 3 4 3  1 2 3 4 3                                                                                  [3,4]                       [2,3,4]                     [1,2,3,4]                                  [4,4]               [3,4,4]    """    stack = []            # increasing stack    res={i:-1 for i in range(len(nums))}    nums2 = nums*2        # handle circularfor i in range(len(nums2)-1, -1, -1):        n = nums2[i]        while stack and nums2[stack[-1]] <= n:            stack.pop()        if stack:            res[i]=nums2[stack[-1]]        stack.append(i)                return [n for idx, n in sorted(res.items(), key=lambda x:x) if idx < len(nums)]`
`def nextGreaterElements(self, nums: List[int]) -> List[int]:    """    array:  a1, a2, a3, ...ai...an                            |            stack: a1>a2>a3 <= ai ?            yes, update res[a3] = ai            no, stack: a1>a2>ai,.. continue until the end            ...    """        stack = []    res={}    nums2 = nums*2  # handle circular    for i, n in enumerate(nums2):        while stack and nums2[stack[-1]] < n:            res[stack.pop()]=n        stack.append(i)                while stack :        res[stack.pop()]=-1    return [n for idx, n in sorted(res.items(), key=lambda x:x if idx < len(nums)]`
`class StockSpanner:def __init__(self):        self.stack = [] # stack to store # of elements <= self, top element is the smallestdef next(self, price: int) -> int:        """                100   80    60    70    60   75    85        stack : 100:1 80:1  60:1  70:2  60:1 75:4  85:6                      100:1 80:1  80:1  70:2 80:1  100:1                            100:1 100:1 80:1 100:1                                        100:1        """        res = 1        while self.stack and self.stack[-1] <= price:            res += self.stack.pop()        self.stack.append([price, res])        return res`
`def removeDuplicateLetters(self, s: str) -> str:    """        stack[] : increasing mono-stack        wc : a char counter to track <char_in_s : count>        for each char in s        Case 1: stack empty : add in stack        Case 2: stack [-1] < current, if already in stack, no need else add in        Case 3: stack [-1] > current, pop stack if there is more <current> left in wc    """    wc = collections.Counter(s)    arr = []    for c in s:        if not arr:            arr.append(c)            wc[c]-=1            continue        if arr[-1] < c:            if c not in arr:                arr.append(c)        elif arr[-1] > c:            if c not in arr:                while arr and arr[-1] >= c and wc[arr[-1]] > 0:                    arr.pop()                arr.append(c)        wc[c]-=1    return ''.join(arr)`

## Other stack related problems but not mono-stack

These are good “start” problems to understand the idea of stack itself .

# Conclusion

Mono-stack is not easy to think of in first place. when there is a problem need us to have an array to track all previous or next “greater” or “smaller” elements and maintein a “from smallest to largest” or “largest to smallest” sequence , this is more likely mono-stack problem.

--

-- ## LORY

A Senior Software Developer/Body builder . to help others enjoy coding and stay healthy