Monotonic Stack

 

Monotonic stack or monotonicly increasing/decreasing stack is a stack which keeps its elements in increasing/decreasing order.

Monotonic stacks are useful when,

- Finding the very previous less element of each element in a vector in O(N) time complexity

- Finding the very next less element of each element in a vector in O(N) time complexity

 

(1) Code Example

To get the very previous less (or equal) element:

- use decreasing stack + use the top element of the stack

nums = [1, 3, 1, 1, 2]

N = len(nums)
stack = []
res = [-1] * N

# the very previous less (or equal) element:
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] > num:
        stack.pop()
    res[i] = stack[-1] if stack else -1
    stack.append(i)

print(res)

To get the very next less or equal element

- use increasing stack + use popped element

nums = [1, 3, 1, 1, 2]

N = len(nums)
stack = []
res = [N] * N

# the very next less or equal element
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] >= num:
        res[stack.pop()] = i
    stack.append(i)

print(res)

 

the very previous bigger or equal element:

nums = [1, 3, 1, 1, 2]

N = len(nums)
stack = []
res = [-1] * N

# the very previous bigger (or equal) element:
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] < num:
        stack.pop()
    res[i] = stack[-1] if stack else -1
    stack.append(i)

print(res)

 

the very next bigger or equal

nums = [1, 3, 1, 1, 2]

N = len(nums)
stack = []
res = [N] * N

# the very next bigger or equal element
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] <= num:
        res[stack.pop()] = i
    stack.append(i)

print(res)

 

(2) Sum of Subarray Minimum

https://leetcode.com/problems/sum-of-subarray-minimums/

Sum of Subarray Minimums - LeetCode

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        N = len(arr)
        
        left = [-1] * N
        right = [N] * N
        
        stack = []
        for i, num in enumerate(arr):
            while stack and arr[stack[-1]] > num:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        stack = []
        for i, num in enumerate(arr):
            while stack and arr[stack[-1]] > num:
                right[stack.pop()] = i
            stack.append(i)
        
        ret = 0
        for i, num in enumerate(arr):
            ret += num * (i - left[i]) * (right[i] - i)
            ret %= (10**9+7)
        return ret