Monotonic Data Structures

Monotonic stacks and queues enforce strict ordering invariants over dynamically filtered sequences, pruning obsolete candidates in amortized $\mathcal{O}(1)$ time per element. From range extrema lookups and histogram geometry to sliding-window signal filtering, monotonic structures convert intractable $\mathcal{O}(n^2)$ and $\mathcal{O}(n\log k)$ lookups into optimal linear scans.

This module explores ordered linear containers that discard dominated elements as new candidates arrive, maintaining a monotonic sub-sequence that guarantees immediate access to extreme values.

By the end of this chapter, you will be able to:

1. Enforce Monotonic Stack Invariants: Implement increasing and decreasing stacks to resolve Next/Previous Greater/Smaller Element queries in amortized $\mathcal{O}(n)$ time.
2. Maximize Geometric Subarrays: Apply monotonic stacks to find the largest rectangular area in a histogram by tracking span boundaries in $\mathcal{O}(n)$ time.
3. Construct Monotonic Deques: Maintain double-ended queues of indices to solve the Sliding Window Maximum problem in strictly $\Theta (n)$ time and $\mathcal{O}(k)$ auxiliary space.
4. Prove Amortized Invariants: Mathematically demonstrate why inner while loops across monotonic structures achieve aggregate $\mathcal{O}(n)$ time through single-push, single-pop guarantees.

A Monotonic Stack is a last-in, first-out container that maintains its stored elements in strictly sorted order (either monotonically increasing or decreasing) from bottom to top:

Given array $A=[2,1,2,4,3]$, determine the first element to the right that is strictly greater than each element. If none exists, assign $-1$.

• Brute Force: Evaluate all pairs $(i,j)$ where $j>i⟹\mathcal{O}(n^2)$ time.
• Monotonic Stack Optimization: Scan right-to-left, popping elements smaller than or equal to $A[i]⟹\mathbf{\Theta }(\mathbf{n})$ linear time.

/**
 * Computes Next Greater Element for every array position.
 * Time Complexity:  O(n) amortized
 * Space Complexity: O(n) auxiliary stack
 */
export function nextGreaterElement(nums: number[]): number[] {
  const n = nums.length;
  const nge = new Array<number>(n);
  const stack: number[] = []; // Monotonically decreasing stack storing values

  // Traverse right-to-left
  for (let i = n - 1; i >= 0; i--) {
    // Discard elements dominated by nums[i]
    while (stack.length > 0 && stack[stack.length - 1] <= nums[i]) {
      stack.pop();
    }

    nge[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
    stack.push(nums[i]);
  }

  return nge;
}

Final Result: nge = [4, 2, 4, -1, -1].

Although an inner while loop executes during iterations, consider the aggregate lifecycle of elements:

• Each index is pushed onto the stack exactly once.
• Each index is popped from the stack at most once.
• The total number of stack operations across the entire algorithm cannot exceed $2n$.
• Therefore, the amortized cost per element is $\mathcal{O}(1)$, yielding total runtime $\mathbf{\Theta }(\mathbf{n})$.

Given bar heights $H=[2,1,5,6,2,3]$, compute the maximum rectangular area formed under the histogram bars.

For each bar $i$, the maximum rectangle with height $H[i]$ spans from its Previous Smaller Element (PSE) to its Next Smaller Element (NSE):

export function largestRectangleArea(heights: number[]): number {
  const stack: number[] = []; // Stores indices
  let maxArea = 0;
  const n = heights.length;

  for (let i = 0; i <= n; i++) {
    const currentHeight = i === n ? 0 : heights[i];

    while (stack.length > 0 && currentHeight < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()!];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}

Given array $A$ of size $n$ and window size $K$, find the maximum value in every contiguous window of length $K$ as it shifts right by 1 step.

A Monotonic Queue maintains array indices in a double-ended queue (deque) adhering to two simultaneous invariants:

1. Value Monotonicity: Indices in the deque correspond to strictly decreasing array values from front to back ($A[D_0]>A[D_1]>\dots$). Consequently, deque.front() always holds the index of the window maximum.
2. Window Expiration: If the front index satisfies $D_0\le i-K$, it has fallen out of window boundaries and is removed from the front.
3. Domination Pruning: Before inserting index $i$, all back indices $j$ where $A[j]\le A[i]$ are popped. If an older element is smaller than a newer element, it can never serve as a window maximum.

export function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  if (n === 0 || k === 0) return [];

  const deque: number[] = []; // Stores indices
  const result: number[] = [];

  for (let i = 0; i < n; i++) {
    // 1. Remove indices outside current window
    if (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }

    // 2. Remove indices with values dominated by nums[i]
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    // 3. Append current element index
    deque.push(i);

    // 4. Record front value once first window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

1. Monotonic Stack: Solves range boundary queries (Next/Previous Greater/Smaller) in $\Theta (n)$ amortized time by discarding non-competitive elements.
2. Histogram Geometry: The area under an irregular histogram decomposes into $n$ candidate rectangles defined by Previous and Next Smaller Element boundaries.
3. Monotonic Deque: Maintains sliding window extrema in linear time by discarding elements that are both older and smaller than incoming candidates.

1. Halim, S., Halim, F., & Skiena, S. S. (2020). Competitive Programming 4: The Lower Bound of Programming Contests. CP4 Pte Ltd.
2. Laaksonen, A. (2020). Guide to Competitive Programming: Learning and Improving Algorithms Through Contests (2nd ed.). Springer.
3. Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.