Skip to content

Monotonic Stack

Table of Contents

739. Daily Temperatures

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, stack, monotonic stack

  • Return an array res such that res[i] is the number of days you have to wait after the ith day to get a warmer temperature.
Index Temp > stack last stack result
0 73 False [ [73, 0] ] 1 - 0 = 1
1 74 True [ [74, 1] ] 2 - 1 = 1
2 75 True [ [75, 2] ] 6 - 2 = 4
3 71 False [ [75, 2], [71, 3] ] 5 - 3 = 2
4 69 False [ [75, 2], [71, 3], [69, 4] ] 5 - 4 = 1
5 72 True [ [75, 2], [72, 5] ] 6 - 5 = 1
6 76 True [ [76, 6] ] 0
7 73 False [[76, 6], [73, 7]] 0
739. Daily Temperatures - Python Solution
from typing import List


# Monotonic Stack
def dailyTemperatures(temperatures: List[int]) -> List[int]:
    res = [0 for _ in range(len(temperatures))]
    stack = []  # [temp, index]

    for i, temp in enumerate(temperatures):
        while stack and temp > stack[-1][0]:
            _, idx = stack.pop()
            res[idx] = i - idx

        stack.append([temp, i])

    return res


print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

1475. Final Prices With a Special Discount in a Shop

496. Next Greater Element I

496. Next Greater Element I - Python Solution
from typing import List


# Monotonic Stack
def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
    next_greater = {}
    stack = []
    result = []

    for num in nums2:
        while stack and num > stack[-1]:
            next_greater[stack.pop()] = num
        stack.append(num)

    for num in nums1:
        result.append(next_greater.get(num, -1))

    return result


nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(nextGreaterElement(nums1, nums2))  # [3, -1, -1]

503. Next Greater Element II

503. Next Greater Element II - Python Solution
from typing import List


# Monotonic Stack
def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)

    return result


nums = [1, 2, 1]
print(nextGreaterElements(nums))  # [2, -1, 2]

1019. Next Greater Node In Linked List

962. Maximum Width Ramp

853. Car Fleet

853. Car Fleet - Python Solution
from typing import List


# Stack
def carFleet(target: int, position: List[int], speed: List[int]) -> int:
    cars = sorted(zip(position, speed), reverse=True)
    stack = []

    for p, s in cars:
        time = (target - p) / s

        if not stack or time > stack[-1]:
            stack.append(time)

    return len(stack)


print(carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3]))  # 3

901. Online Stock Span

  • LeetCode | LeetCode CH (Medium)

  • Tags: stack, design, monotonic stack, data stream

  • Design a class StockSpanner to return the number of consecutive days (including the current day) the price of the stock has been less than or equal to the current price.
901. Online Stock Span - Python Solution
from typing import List


# Monotonic Stack
class StockSpanner:

    def __init__(self):
        self.stack = [(-1, float("inf"))]
        self.cur_day = -1

    def next(self, price: int) -> int:
        while price >= self.stack[-1][1]:
            self.stack.pop()
        self.cur_day += 1
        self.stack.append((self.cur_day, price))
        return self.cur_day - self.stack[-2][0]


obj = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
print([obj.next(price) for price in prices])  # [1, 1, 1, 2, 1, 4, 6]

1124. Longest Well-Performing Interval

1793. Maximum Score of a Good Subarray

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, two pointers, binary search, stack, monotonic stack

456. 132 Pattern

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, binary search, stack, monotonic stack, ordered set

456. 132 Pattern - Python Solution
from typing import List


# Monotonic Stack
def find132pattern(nums: List[int]) -> bool:
    n = len(nums)
    if n < 3:
        return False

    stack = []
    second_max = float("-inf")

    for i in range(n - 1, -1, -1):
        if nums[i] < second_max:
            return True

        while stack and stack[-1] < nums[i]:
            second_max = stack.pop()

        stack.append(nums[i])

    return False


nums = [-1, 3, 2, 0]
print(find132pattern(nums))  # True

3113. Find the Number of Subarrays Where Boundary Elements Are Maximum

2866. Beautiful Towers II

1944. Number of Visible People in a Queue

2454. Next Greater Element IV

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, stack, sorting, heap priority queue, monotonic stack

1130. Minimum Cost Tree From Leaf Values

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, stack, greedy, monotonic stack

2289. Steps to Make Array Non-decreasing

1776. Car Fleet II

3221. Maximum Array Hopping Score II

1966. Binary Searchable Numbers in an Unsorted Array

2832. Maximal Range That Each Element Is Maximum in It

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

Comments