🐟 Blog

Monotonic Stack

April 05, 2021

Next greater element

This is the archetype of monotonic stack problems.


You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.

Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number xx in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.


Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]


The problem implies that nums2 is the source data, and we should process this array in some way so that we can iterate over nums1 and return the answer for each element.

To answer these next greater element questions, we can use a monotonic stack. It is just a regular stack we maintain in such a way that the elements inside at any given time are monotonically increasing or decreasing.


Say we have an element 33.

  • If the next element is 22, we don’t know the next greater element of 33 yet. So we need to stash this 22, and wait for its next greater element to appear.
  • If the next element is 44, we have found the next greater element of 33, as well as any previously stashed element xx before 33 such that 3<x<43 < x < 4.
fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
  val dict = hashMapOf<Int, Int>()
  val stack = Stack<Int>()

  for (n in nums2) {
    while (!stack.isEmpty() && stack.peek() < n) {      dict[stack.pop()] = n    }    stack.push(n)  }

  val ret = IntArray(nums1.size)
  for (i in ret.indices) {
    ret[i] = dict.getOrDefault(nums1[i], -1)
  return ret

The highlighted part of the code is the idiom for maintaining a monotonic stack.



Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.


To handle circularity, we can concatenate two copies of the nums array. The modulo operation % helps us achieve this without allocating extra space. Then the code is almost the same as Next Greater Element I.

Notice we store the array index rather than array item in the monotonic stack.

fun nextGreaterElements(nums: IntArray): IntArray {
  val stack = Stack<Int>()
  val ret = IntArray(nums.size) { -1 }

  // i in [0, 2 * nums.size)
  for (i in 0 until (2 * nums.size - 1)) {
    // adjusted index
    val ii = i % nums.size
    while (!stack.isEmpty() && nums[stack.peek()] < nums[ii]) {      ret[stack.pop()] = nums[ii]    }    stack.push(ii)  }

  return ret

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

stock quotes: [100, 80, 60, 70, 60, 75, 85]
stock spans: [1, 1, 1, 2, 1, 4, 6]


class StockSpanner {
  fun next(price: Int): Int {/**/}



class StockSpanner() {
  data class Data(val price: Int, val span: Int)
  val stack: Deque<Data> = ArrayDeque()

  fun next(price: Int): Int {
    var n = 1
    while (!stack.isEmpty() && stack.peek().price <= price) {      n += stack.pop().span    }    stack.push(Data(price, n))
    return n


The question asks for the maximum number of consecutive days before for which the price is \leq today’s price. In other words, if we find the previous greater element, we’ve got the answer.

When the top of the stack is \leq today’s price, we are effectively merging previous records into today’s record, since we only care about previous greater element when new quotes come in. If the element on top of the stack is smaller, it doesn’t matter anymore.


Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 00 instead.


fun dailyTemperatures(T: IntArray): IntArray {
  val stack: Deque<Int> = ArrayDeque()
  val ret = IntArray(T.size)
  for (i in T.indices) {
    while (!stack.isEmpty() && T[stack.peek()] < T[i]) {      val j = stack.pop()      ret[j] = i - j    }    stack.push(i)
  return ret

This section is WIP.

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that

i<j<knums[i]<nums[k]<nums[j].i < j < k\\ nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.


Iterate through the numbers and presume the current element is the 33 in the pattern.

  1. The 1 is to the left of the current element. The best candidate is the smallest item to the left.
  2. the 2 is to the right of the current element. The best candidate is the next greater element to the right

Compare these three numbers and if they match the pattern we can return true.

We can solve the first part by dynamic programming, and the second part by a monotonic stack.


© Attribution Required | 转载请注明原作者与本站链接
© 2022 yujinyan.me