Monotonic Stack

Apr 5, 2021

Next greater element

This is the archetype of monotonic stack problems.

easy

№ 496. Next Greater Element I

67% ac·力扣中文站

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 $x$ in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.

Example:

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.

Intuition

Say we have an element $3$ .

If the next element is $2$ , we don’t know the next greater element of $3$ yet. So we need to stash this $2$ , and wait for its next greater element to appear.
If the next element is $4$ , we have found the next greater element of $3$ , as well as any previously stashed element $x$ before $3$ such that $3 < x < 4$ .

fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {
  val dict = hashMapOf<Int, Int>()
  val stack = Stack<Int>()

  // highlight-range{2-5}
  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.

Variations

medium

№ 503. Next Greater Element II

62% ac·力扣中文站

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
    // highlight-range{1-4}
    while (!stack.isEmpty() && nums[stack.peek()] < nums[ii]) {
      ret[stack.pop()] = nums[ii]
    }
    stack.push(ii)
  }

  return ret
}

medium

№ 901. Online Stock Span

52% ac·力扣中文站

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.

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

Skeleton:

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

Solution:

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

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

Intuition:

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.

medium

№ 739. Daily Temperatures

66% ac·力扣中文站

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 $0$ instead.

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

medium

№ 456. 132 Pattern

29% ac·力扣中文站

🚧

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 < 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 $3$ in the pattern.

The 1 is to the left of the current element. The best candidate is the smallest item to the left.
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.

Next greater element

Intuition

Variations

Reference