Monotonic Stack¶
Table of Contents¶
- 739. Daily Temperatures (Medium)
- 1475. Final Prices With a Special Discount in a Shop (Easy)
- 496. Next Greater Element I (Easy)
- 503. Next Greater Element II (Medium)
- 1019. Next Greater Node In Linked List (Medium)
- 962. Maximum Width Ramp (Medium)
- 853. Car Fleet (Medium)
- 901. Online Stock Span (Medium)
- 1124. Longest Well-Performing Interval (Medium)
- 1793. Maximum Score of a Good Subarray (Hard)
- 456. 132 Pattern (Medium)
- 3113. Find the Number of Subarrays Where Boundary Elements Are Maximum (Hard)
- 2866. Beautiful Towers II (Medium)
- 1944. Number of Visible People in a Queue (Hard)
- 2454. Next Greater Element IV (Hard)
- 1130. Minimum Cost Tree From Leaf Values (Medium)
- 2289. Steps to Make Array Non-decreasing (Medium)
- 1776. Car Fleet II (Hard)
- 3221. Maximum Array Hopping Score II (Medium) 👑
- 1966. Binary Searchable Numbers in an Unsorted Array (Medium) 👑
- 2832. Maximal Range That Each Element Is Maximum in It (Medium) 👑
- 2282. Number of People That Can Be Seen in a Grid (Medium) 👑
739. Daily Temperatures¶
"""
- 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 |
"""
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¶
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¶
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¶
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¶
"""
- 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.
"""
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]
if __name__ == "__main__":
ss = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
print([ss.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¶
456. 132 Pattern¶
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