After solved 1000 medium leetcode found thes patterns — Mono-Stack
Continue the leetcode pattern series : DFS, BFS and DP , BackTracking . This article I summary and explain with some high ranking problems for 1 more classic pattern — monolithic stack .
Lets get into it .
Try to identify the pattern below for stack1 and stack2 .
index : 0 1 2 3 4 5 6 7
Array : [3, 7, 1, 4, 7, 2, 9, 8]
stack1: [3]:index=0
[3,7]:index=1
[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=7
Array : [3, 7, 1, 4, 7, 2, 9, 8]
stack2: [3]:index=0
[7]:index=1
[7,1]:index=2
[7,4]:index=3
[7,7]:index=4
[7,7,2]:index=5
[9]:index=6
[9,8]:index=7Yes, you got it .
This is the idea of monolithic stack . stack1 is “increasing stack” — [elements before self , from biggest to smallest] ≤ self ; stack2 is “decreasing stack” — [elements before self from smallest to biggest] ≥ self
Implementation of a decreasing stack .
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])Now lets see some leetcode problems .
Thought process. This is classic mono-stack problem. to know the “next greater element” , need to loop from last element to first, and using a “decreasing stack” to track the “next greater” element .
def nextGreaterElements(self, nums: List[int]) -> List[int]:
"""
1 2 3 4 3 1 2 3 4 3
[3]
[4]
[3,4]
[2,3,4]
[1,2,3,4]
[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[0]) if idx < len(nums)]
Or, you could also loop from first element, use an increasing stack . and update result[stack.pop()]=current_element
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[0] if idx < len(nums)]
Thought process . Since the rule to “span” previous element is when value<self . so we need a decreasing stack to track the [element before self]>self, while popping stack, res[current element] = res[top element on stack]+1, here we also need use res[] to track the answer for each element .
Explained with an example in comments .
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][0] <= price:
res += self.stack.pop()[1]
self.stack.append([price, res])
return res
Last one.
Thought process explained in code comments. the core idea is maintein a increasing stack + greedy thinking (check if there are more char left in char counter)
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)More mono stack problems for practice .
581. Shortest Unsorted Continuous Subarray
946. Validate Stack Sequences 962. Maximum Width Ramp
Other stack related problems but not mono-stack
These are good “start” problems to understand the idea of stack itself .
150. Evaluate Reverse Polish Notation (This is basic classic stack problem, beginner can start here)
227. Basic Calculator II (This is another basic classic stack problem, beginner can start here)
331. Verify Preorder Serialization of a Binary Tree
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.
Thanks for reading , happy leetcoding !
