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

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=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]
[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 circular
for 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)]
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)]
class StockSpanner:def __init__(self):
self.stack = [] # stack to store # of elements <= self, top element is the smallest
def 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
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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
LORY

LORY

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