LeetCode Patterns ·

🎯 Monotonic Stack

1️⃣ Core Framework

When discussing Monotonic Stack, I frame it as:

What problem pattern it solves
Increasing stack vs decreasing stack
Next greater element
Next smaller element
Previous greater / previous smaller
Daily temperatures
Circular next greater element
Largest rectangle in histogram
Sum of subarray minimums
Common edge cases and senior-level explanation

2️⃣ What Problem Are We Solving?

A monotonic stack is used when we need to find the nearest greater or smaller element around each position.

It is commonly used for:

Next greater element
Next smaller element
Previous greater element
Previous smaller element
Daily temperatures
Stock span
Largest rectangle in histogram
Sum of subarray minimums
Sum of subarray ranges
Trapping rain water variants
Circular array next greater element

The core idea is:

Maintain a stack with monotonic order.
When the current element breaks the order,
pop elements and resolve answers for them.

👉 Interview Answer

A monotonic stack is a stack that keeps elements in increasing or decreasing order.

It is useful for finding nearest greater or nearest smaller elements efficiently.

When the current element breaks the monotonic invariant, we pop elements from the stack and use the current element as their boundary or answer.

Most monotonic stack problems run in O(n) time because each element is pushed once and popped once.

3️⃣ Why Monotonic Stack Works

Brute Force Problem

For each element, we may want to scan left or right:

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[j] > nums[i]:
            answer[i] = nums[j]
            break

This is:

O(n²)

Monotonic Stack Optimization

Instead of scanning repeatedly, we keep unresolved candidates in a stack.

stack = unresolved indexes

When a new value arrives:

If it can resolve previous elements,
pop them and fill their answer.

Why O(n)?

Each index is:

pushed once
popped once

So even though there is a while loop inside the for loop, total work is linear.

Time: O(n)
Space: O(n)

👉 Interview Answer

Monotonic stack works because it keeps only useful unresolved candidates.

When the current element makes some previous elements no longer useful, those elements are popped and resolved.

Since each element can enter and leave the stack only once, the total complexity is O(n), not O(n²).

4️⃣ Increasing Stack vs Decreasing Stack

Monotonic Increasing Stack

The stack values increase from bottom to top.

bottom → top
small → large

Example:

[1, 3, 5, 7]

Usually useful for:

next smaller element
previous smaller element
histogram left/right smaller boundary

Monotonic Decreasing Stack

The stack values decrease from bottom to top.

bottom → top
large → small

Example:

[9, 7, 5, 2]

Usually useful for:

next greater element
previous greater element
daily temperatures
stock span

Important Rule

The comparison decides what gets popped.

while stack and current breaks monotonic order:
    pop

👉 Interview Answer

If I need to find a next greater element, I often use a decreasing stack.

If the current element is greater than the stack top, it resolves the stack top.

If I need to find a next smaller element, I often use an increasing stack.

The stack direction depends on which boundary I want to find.

5️⃣ What Does the Stack Store?

Store Indexes

Most of the time, store indexes:

stack.append(i)

Why?

Because indexes let us access:

nums[index]
distance = i - index
position-based answer

Store Values

Sometimes values are enough:

stack.append(num)

Useful when:

only value is needed
no distance or index needed

Store Pairs

Sometimes store compressed state:

stack.append((value, count))
stack.append((price, span))

Useful for:

stock span
duplicate compression
contribution counting

👉 Interview Answer

In monotonic stack problems, I usually store indexes rather than values.

Indexes allow me to compute distances, update answer positions, and still access the original value.

If the problem only needs values, storing values is fine.

If duplicate counts or compressed spans matter, I may store pairs.

6️⃣ Next Greater Element

Problem

For each element, find the next greater element on its right.

nums = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]

Stack Invariant

Use a decreasing stack of unresolved indexes.

stack stores indexes whose next greater element is not found yet
values are decreasing from bottom to top

Code

def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Key Insight

When current value is greater than stack top:

current value is the next greater element for stack top

Why?

Because it is the first greater value we encounter while scanning left to right.

👉 Interview Answer

For next greater element, I maintain a decreasing stack of indexes.

The stack stores elements whose next greater element has not been found.

When the current value is greater than the value at the stack top, the current value is the next greater element for that index.

I pop and resolve until the decreasing order is restored.

7️⃣ Next Smaller Element

Problem

For each element, find the next smaller element on its right.

nums = [2, 1, 4, 3]
answer = [1, -1, 3, -1]

Stack Invariant

Use an increasing stack of unresolved indexes.

stack stores indexes whose next smaller element is not found yet
values are increasing from bottom to top

Code

def next_smaller_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] > num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Key Insight

When current value is smaller than stack top:

current value is the next smaller element for stack top

👉 Interview Answer

For next smaller element, I maintain an increasing stack.

When the current value is smaller than the value at the stack top, it becomes the next smaller element for that index.

Then I pop that index and continue resolving earlier unresolved elements.

8️⃣ Previous Greater Element

Problem

For each element, find the nearest greater element on its left.

nums = [2, 1, 4, 3]
answer = [-1, 2, -1, 4]

Code

def previous_greater_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Stack Invariant

Maintain a decreasing stack.

Before pushing current index:

stack top is the nearest greater element on the left

👉 Interview Answer

For previous greater element, I scan from left to right and maintain a decreasing stack.

Before processing the current value, I remove all values that are smaller than or equal to it, because they cannot be the previous greater element for current or future values.

If the stack is not empty, the top is the nearest greater element.

9️⃣ Previous Smaller Element

Problem

For each element, find the nearest smaller element on its left.

nums = [2, 1, 4, 3]
answer = [-1, -1, 1, 1]

Code

def previous_smaller_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Stack Invariant

Maintain an increasing stack.

Before pushing current index:

stack top is the nearest smaller element on the left

👉 Interview Answer

For previous smaller element, I maintain an increasing stack.

I pop values that are greater than or equal to the current value.

After popping, if the stack is not empty, the top is the nearest smaller element on the left.

🔟 Strict vs Non-Strict Comparison

Why It Matters

For duplicates, this choice matters:

<
<=
>
>=

Example:

nums = [2, 2, 2]

Depending on the problem, equal values may need to be:

kept in stack
or
popped from stack

Common Choices

For previous greater:

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

For previous greater or equal:

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

For previous smaller:

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

For previous smaller or equal:

while stack and nums[stack[-1]] > nums[i]:
    stack.pop()

Senior-Level Rule

Define exactly what boundary you need:

strictly greater?
greater or equal?
strictly smaller?
smaller or equal?

👉 Interview Answer

Duplicate handling is one of the most important details in monotonic stack.

I decide whether equal values should be popped based on whether the problem needs a strict or non-strict boundary.

For contribution-counting problems, I often intentionally use strict comparison on one side and non-strict comparison on the other side to avoid double counting.

1️⃣1️⃣ Daily Temperatures

Problem

For each day, return how many days must pass until a warmer temperature.

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer       = [1, 1, 4, 2, 1, 1, 0, 0]

Pattern

This is next greater element by distance.

next warmer temperature = next greater element
answer = next_index - current_index

Code

def daily_temperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            previous_index = stack.pop()
            result[previous_index] = i - previous_index

        stack.append(i)

    return result

👉 Interview Answer

Daily Temperatures is a next greater element problem.

The stack stores indexes of days whose warmer future day has not been found.

When the current temperature is higher than the temperature at the stack top, the current day resolves that previous day.

The answer is the distance between the two indexes.

1️⃣2️⃣ Next Greater Element II - Circular Array

Problem

Find next greater element in a circular array.

nums = [1, 2, 1]
answer = [2, -1, 2]

Key Idea

Loop twice over the array.

for i in range(2 * n):
    index = i % n

The second pass simulates circular behavior.

Code

def next_greater_elements_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        index = i % n

        while stack and nums[stack[-1]] < nums[index]:
            prev_index = stack.pop()
            result[prev_index] = nums[index]

        if i < n:
            stack.append(index)

    return result

Why Push Only in First Pass?

First pass: create unresolved candidates
Second pass: only resolve candidates

If we push again in the second pass, we may duplicate indexes.

👉 Interview Answer

For circular next greater element, I simulate circular traversal by iterating through the array twice.

I use index modulo n to map back into the original array.

I push indexes only during the first pass, and use the second pass only to resolve remaining elements.

1️⃣3️⃣ Online Stock Span

Problem

For each price, return how many consecutive days including today had price less than or equal to today’s price.

prices = [100, 80, 60, 70, 60, 75, 85]
span   = [1,   1,  1,  2,  1,  4,  6]

Code

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price):
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            previous_price, previous_span = self.stack.pop()
            span += previous_span

        self.stack.append((price, span))
        return span

Stack Invariant

The stack keeps prices in decreasing order.

Each item stores:

(price, compressed_span)

👉 Interview Answer

Stock Span uses a monotonic decreasing stack.

Each stack entry stores a price and its compressed span.

When the current price is greater than or equal to the top price, I pop the top and merge its span into the current span.

This gives amortized O(1) time per query.

1️⃣4️⃣ Largest Rectangle in Histogram

Problem

Given bar heights, find the largest rectangle area.

heights = [2, 1, 5, 6, 2, 3]
answer = 10

Key Insight

For each bar, we need:

first smaller bar on the left
first smaller bar on the right

Then:

width = right_smaller_index - left_smaller_index - 1
area = height * width

Code

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    extended = heights + [0]

    for i, height in enumerate(extended):
        while stack and extended[stack[-1]] > height:
            h = extended[stack.pop()]
            left_smaller_index = stack[-1] if stack else -1
            width = i - left_smaller_index - 1
            max_area = max(max_area, h * width)

        stack.append(i)

    return max_area

What Happens When We Pop?

When a bar is popped:

current index = first smaller element on the right
new stack top = first smaller element on the left

So we can calculate the largest rectangle where the popped bar is the minimum height.

👉 Interview Answer

Largest Rectangle in Histogram uses a monotonic increasing stack.

The stack stores indexes with increasing heights.

When the current height is smaller than the height at the stack top, the popped bar has found its right smaller boundary.

After popping, the new stack top is its left smaller boundary.

This gives the maximum width where the popped bar is the limiting height.

1️⃣5️⃣ Why Add Sentinel Value?

Problem Without Sentinel

At the end of the array, some bars may remain unresolved in the stack.

Example:

heights = [1, 2, 3, 4]

No smaller bar appears on the right.

Add Zero

extended = heights + [0]

The final zero forces every remaining bar to be popped.

Alternative

You can also process remaining stack after the loop.

while stack:
    process remaining bars

But sentinel is cleaner.

👉 Interview Answer

In histogram problems, I often add a sentinel zero at the end.

This forces all remaining bars in the stack to be popped and processed.

It avoids writing a separate cleanup loop and keeps the logic consistent.

1️⃣6️⃣ Maximal Rectangle

Problem

Given a binary matrix, find the largest rectangle containing only 1s.

Key Idea

Convert each row into a histogram.

height[c] = number of consecutive 1s ending at current row

Then run:

largest rectangle in histogram

Code

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    heights = [0] * cols
    best = 0

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == "1":
                heights[c] += 1
            else:
                heights[c] = 0

        best = max(best, largest_rectangle_area(heights))

    return best

👉 Interview Answer

Maximal Rectangle reduces a 2D matrix problem to repeated histogram problems.

For each row, I treat it as the base of a histogram.

Each column height represents consecutive ones ending at that row.

Then I apply the largest rectangle in histogram algorithm.

1️⃣7️⃣ Sum of Subarray Minimums

Problem

Given an array, return the sum of the minimum value of every subarray.

arr = [3, 1, 2, 4]
subarray minimums:
[3] = 3
[3,1] = 1
[3,1,2] = 1
[3,1,2,4] = 1
[1] = 1
[1,2] = 1
[1,2,4] = 1
[2] = 2
[2,4] = 2
[4] = 4

answer = 17

Contribution Thinking

Instead of enumerating every subarray, ask:

For each arr[i],
how many subarrays use arr[i] as the minimum?

If:

left_count = number of choices for left boundary
right_count = number of choices for right boundary

Then contribution is:

arr[i] * left_count * right_count

Boundary Choice

To avoid double counting duplicates, use asymmetric comparisons:

previous strictly smaller
next smaller or equal

or:

previous smaller or equal
next strictly smaller

Either is fine if used consistently.

Code

def sum_subarray_mins(arr):
    mod = 10 ** 9 + 7
    n = len(arr)

    prev_less = [-1] * n
    next_less_equal = [n] * n

    stack = []

    # previous strictly less
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()

        if stack:
            prev_less[i] = stack[-1]

        stack.append(i)

    stack = []

    # next less or equal
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()

        if stack:
            next_less_equal[i] = stack[-1]

        stack.append(i)

    result = 0

    for i in range(n):
        left_count = i - prev_less[i]
        right_count = next_less_equal[i] - i
        result += arr[i] * left_count * right_count

    return result % mod

👉 Interview Answer

Sum of Subarray Minimums is a monotonic stack contribution problem.

Instead of enumerating all subarrays, I calculate how many subarrays use each element as the minimum.

For each index, I find the previous smaller boundary and next smaller boundary.

The number of valid subarrays is left choices multiplied by right choices.

To handle duplicates correctly, I use strict comparison on one side and non-strict comparison on the other side.

1️⃣8️⃣ Sum of Subarray Ranges

Problem

For every subarray:

range = max - min

Return the sum of all subarray ranges.

Key Idea

sum of ranges
= sum of subarray maximums - sum of subarray minimums

Use monotonic stack twice:

one pass pattern for contribution as maximum
one pass pattern for contribution as minimum

Contribution Formula

For each element:

contribution = value * left_count * right_count

As maximum:

find previous greater and next greater boundary

As minimum:

find previous smaller and next smaller boundary

👉 Interview Answer

Sum of Subarray Ranges can be solved by contribution counting.

The range of a subarray is maximum minus minimum.

So I compute each element’s total contribution as a maximum, subtract its total contribution as a minimum, and sum the results.

Monotonic stacks help find how far each element can extend as max or min.

1️⃣9️⃣ Remove K Digits

Problem

Remove k digits from a number string so the remaining number is smallest possible.

num = "1432219", k = 3
answer = "1219"

Key Idea

Maintain an increasing stack of digits.

If current digit is smaller than stack top:

pop stack top while k > 0

Because removing a larger earlier digit makes the number smaller.

Code

def remove_k_digits(num, k):
    stack = []

    for digit in num:
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1

        stack.append(digit)

    while k > 0:
        stack.pop()
        k -= 1

    result = "".join(stack).lstrip("0")

    return result if result else "0"

👉 Interview Answer

Remove K Digits uses a monotonic increasing stack.

To make the number as small as possible, when the current digit is smaller than the previous digit, I remove the previous larger digit if I still have removals left.

After processing all digits, if k remains, I remove digits from the end.

Finally, I strip leading zeros.

2️⃣0️⃣ Trapping Rain Water With Stack

Problem

Given bar heights, calculate how much water can be trapped.

height = [0,1,0,2,1,0,1,3,2,1,2,1]
answer = 6

Stack Idea

Use stack to store indexes of bars.

When current bar is higher than stack top:

we may have found a right boundary

Pop the valley bottom and calculate water using:

bounded_height = min(left_boundary_height, right_boundary_height) - bottom_height
width = right_index - left_index - 1
water = bounded_height * width

Code

def trap(height):
    stack = []
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()

            if not stack:
                break

            left = stack[-1]
            width = i - left - 1
            bounded_height = min(height[left], h) - height[bottom]
            water += width * bounded_height

        stack.append(i)

    return water

👉 Interview Answer

Trapping Rain Water can be solved with a monotonic stack.

The stack stores indexes of bars.

When the current bar is higher than the stack top, the popped bar can act as the bottom of trapped water.

If there is still a left boundary in the stack, I compute water using the shorter boundary height minus the bottom height.

2️⃣1️⃣ When Monotonic Stack Applies

Good Fit

Use monotonic stack when the problem asks for:

nearest greater element
nearest smaller element
next greater element
previous greater element
next smaller element
previous smaller element
span until greater/smaller
first boundary where condition breaks
contribution as minimum or maximum

Problem Signals

Look for words like:

next greater
next warmer
previous smaller
nearest smaller
span
histogram
rectangle
subarray minimum
subarray maximum
remove digits
first smaller boundary

👉 Interview Answer

I consider monotonic stack when the problem asks for nearest greater or smaller elements, or when each element needs a boundary on the left and right.

It is also useful for contribution-counting problems, where we need to know how many subarrays use an element as the minimum or maximum.

2️⃣2️⃣ When Monotonic Stack Does Not Apply

Not Good Fit

Monotonic stack is usually not ideal when:

The condition is not based on nearest greater/smaller boundary.
The problem needs global sorting.
The problem needs arbitrary range query.
The problem needs shortest path.
The problem is better modeled by heap, binary search, or DP.

Better Alternatives

Problem Type	Better Pattern
Need global minimum repeatedly	Heap
Need range sum query	Prefix Sum
Need range max/min query	Segment Tree / Sparse Table
Need shortest path	BFS / Dijkstra
Need sorted order globally	Sorting / Binary Search
Need optimal substructure	Dynamic Programming

👉 Interview Answer

Monotonic stack is specialized for nearest boundary problems.

If the problem requires global ordering, repeated arbitrary range queries, shortest path, or optimal substructure, another pattern such as heap, segment tree, BFS, or DP may be more appropriate.

2️⃣3️⃣ Common Edge Cases

Empty Input

nums = []

Single Element

nums = [5]

Strictly Increasing Array

[1, 2, 3, 4]

May cause many pops in next greater problems.

Strictly Decreasing Array

[4, 3, 2, 1]

May leave many unresolved elements.

Duplicates

[2, 2, 2]

Need clear strict vs non-strict comparison.

Circular Arrays

Need two passes or modulo indexing.

👉 Interview Answer

Common edge cases include empty input, single element, strictly increasing arrays, strictly decreasing arrays, duplicates, and circular arrays.

Duplicates are especially important because the choice between strict and non-strict comparison changes the result.

2️⃣4️⃣ Complexity Analysis

Time Complexity

Most monotonic stack algorithms are:

O(n)

Because each element is:

pushed once
popped once

Space Complexity

Usually:

O(n)

for the stack and result array.

Amortized Analysis

Even though the code may look like:

for i in range(n):
    while stack:
        stack.pop()

It is not O(n²), because each element can only be popped once globally.

👉 Interview Answer

Monotonic stack is usually O(n) time and O(n) space.

The important point is amortized analysis.

Although there may be a while loop inside the for loop, each element is pushed once and popped once, so the total number of stack operations is linear.

2️⃣5️⃣ Common Mistakes

Mistake 1: Wrong Stack Direction

Using increasing stack when we need decreasing stack.

Mistake 2: Storing Values Instead of Indexes

If the problem asks for distance, width, or position, we usually need indexes.

Mistake 3: Wrong Duplicate Handling

Using:

when the problem needs:

<=

or vice versa.

Mistake 4: Forgetting Sentinel

Histogram problems often need:

heights + [0]

or a cleanup loop.

Mistake 5: Not Explaining Amortized O(n)

Interviewers may ask:

Why is this not O(n²)?

Mistake 6: Confusing Next and Previous Boundaries

Next boundary is usually resolved when popping.

Previous boundary is usually read from stack top before pushing.

👉 Interview Answer

Common mistakes include using the wrong monotonic direction, storing values when indexes are needed, mishandling duplicates, forgetting sentinel values, and confusing next-boundary logic with previous-boundary logic.

I avoid these by defining the stack invariant before writing code.

2️⃣6️⃣ Standard Templates

Next Greater Element Template

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Next Smaller Element Template

def next_smaller(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] > num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Previous Greater Element Template

def previous_greater(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Previous Smaller Element Template

def previous_smaller(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Circular Next Greater Template

def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        index = i % n

        while stack and nums[stack[-1]] < nums[index]:
            prev = stack.pop()
            result[prev] = nums[index]

        if i < n:
            stack.append(index)

    return result

Histogram Template

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    extended = heights + [0]

    for i, height in enumerate(extended):
        while stack and extended[stack[-1]] > height:
            h = extended[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, h * width)

        stack.append(i)

    return max_area

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

A monotonic stack is a stack that maintains elements in increasing or decreasing order.

It is mainly used for nearest greater or nearest smaller boundary problems.

The stack usually stores unresolved indexes. These are elements whose next greater, next smaller, or boundary has not been found yet.

When the current element breaks the monotonic invariant, we pop elements from the stack and resolve their answers.

For next greater element, I maintain a decreasing stack. When the current value is greater than the value at the stack top, the current value becomes the next greater element for that popped index.

For next smaller element, I maintain an increasing stack. When the current value is smaller than the stack top, it resolves the next smaller answer.

For previous greater or previous smaller element, I usually pop invalid candidates first. Then the stack top becomes the nearest valid previous boundary.

A key detail is duplicate handling. The difference between strict and non-strict comparisons matters. For contribution-counting problems, such as sum of subarray minimums, I often use strict comparison on one side and non-strict comparison on the other side to avoid double counting.

Largest Rectangle in Histogram is a classic monotonic stack problem. I maintain an increasing stack of bar indexes. When the current bar is shorter, the popped bar has found its right smaller boundary. The new stack top gives the left smaller boundary. That lets me compute the largest rectangle where the popped bar is the limiting height.

Monotonic stack is also useful for circular arrays by scanning twice, and for contribution problems by counting how far each element can extend as minimum or maximum.

The complexity is usually O(n) time and O(n) space. Even though there is often a while loop inside the for loop, each element is pushed once and popped once, so the total number of stack operations is linear.

At a senior level, I would always explain: what the stack stores, whether it is increasing or decreasing, what invariant it maintains, what condition causes popping, what answer is resolved when popping, and how duplicates are handled.

⭐ Final Insight

Monotonic Stack 的核心不是“用 stack 找 next greater”。

它的核心是维护一个有序的 unresolved candidates 集合。

Senior-level 的重点是：

stack 是 increasing 还是 decreasing， stack 里存 index 还是 value， pop 的时候解决了什么问题， stack top 代表什么 boundary， duplicates 用 strict 还是 non-strict comparison，以及为什么整体是 amortized O(n)。

能讲清楚这些， Monotonic Stack 就是一种处理 nearest boundary 和 contribution counting 的强大算法模式。

中文部分

🎯 Monotonic Stack

1️⃣ 核心框架

讨论 Monotonic Stack 时，我通常从：

它解决什么问题
Increasing stack vs decreasing stack
Next greater element
Next smaller element
Previous greater / previous smaller
Daily temperatures
Circular next greater element
Largest rectangle in histogram
Sum of subarray minimums
常见 edge cases 和高级工程师解释方式

2️⃣ 要解决什么问题？

Monotonic stack 用于寻找每个位置附近最近的 greater 或 smaller element。

它常用于：

Next greater element
Next smaller element
Previous greater element
Previous smaller element
Daily temperatures
Stock span
Largest rectangle in histogram
Sum of subarray minimums
Sum of subarray ranges
Trapping rain water variants
Circular array next greater element

核心思想是：

维护一个单调有序的 stack。
当当前元素破坏单调性时，
pop stack 中的元素，并为它们确定答案。

👉 面试回答

Monotonic stack 是一种保持 increasing 或 decreasing order 的 stack。

它适合高效寻找 nearest greater 或 nearest smaller element。

当当前元素破坏 stack 的 monotonic invariant 时，我们 pop stack 中的元素，并用当前元素作为它们的 boundary 或 answer。

大多数 monotonic stack 问题是 O(n)，因为每个元素最多 push 一次、pop 一次。

3️⃣ 为什么 Monotonic Stack 有效？

暴力解法

对每个元素，如果我们向右扫描找第一个更大值：

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[j] > nums[i]:
            answer[i] = nums[j]
            break

复杂度是：

O(n²)

Monotonic Stack 优化

我们不重复扫描。

而是维护一个 stack：

stack = unresolved indexes

当新元素出现时：

如果它可以解决之前的元素，
就 pop 并填答案。

为什么是 O(n)？

每个 index 只会：

push once
pop once

所以即使 for loop 里面有 while loop，总 work 仍然是 linear。

Time: O(n)
Space: O(n)

👉 面试回答

Monotonic stack 有效，是因为它只保留有用的 unresolved candidates。

当当前元素让一些之前的元素不再有必要继续留在 stack 中时，这些元素会被 pop 并确定答案。

因为每个元素最多进 stack 一次、出 stack 一次，所以总复杂度是 O(n)，不是 O(n²)。

4️⃣ Increasing Stack vs Decreasing Stack

Monotonic Increasing Stack

Stack 中的 values 从 bottom 到 top 递增。

bottom → top
small → large

Example:

[1, 3, 5, 7]

通常用于：

next smaller element
previous smaller element
histogram left/right smaller boundary

Monotonic Decreasing Stack

Stack 中的 values 从 bottom 到 top 递减。

bottom → top
large → small

Example:

[9, 7, 5, 2]

通常用于：

next greater element
previous greater element
daily temperatures
stock span

Important Rule

比较条件决定谁会被 pop。

while stack and current breaks monotonic order:
    pop

👉 面试回答

如果我要找 next greater element，我通常使用 decreasing stack。

如果当前元素比 stack top 更大，它就可以 resolve stack top。

如果我要找 next smaller element，我通常使用 increasing stack。

Stack 的方向取决于我要找 greater boundary 还是 smaller boundary。

5️⃣ Stack 里存什么？

存 Indexes

大多数时候，存 index：

stack.append(i)

因为 index 可以让我们拿到：

nums[index]
distance = i - index
position-based answer

存 Values

有时只存 value 就够了：

stack.append(num)

适用于：

只关心 value
不需要距离或位置

存 Pairs

有时需要存压缩状态：

stack.append((value, count))
stack.append((price, span))

适用于：

stock span
duplicate compression
contribution counting

👉 面试回答

在 monotonic stack 题里，我通常存 index 而不是 value。

因为 index 可以用来计算距离、宽度、位置，也可以通过 nums[index] 取回 value。

如果题目只需要 value，存 value 也可以。

如果涉及 duplicate count 或 compressed span，我可能会存 pair。

6️⃣ Next Greater Element

Problem

对每个元素，找到它右边第一个更大的元素。

nums = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]

Stack Invariant

使用 decreasing stack 存 unresolved indexes。

stack 存还没有找到 next greater element 的 indexes
values 从 bottom 到 top 递减

Code

def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Key Insight

当 current value 大于 stack top：

current value 就是 stack top 的 next greater element

为什么？

因为我们从左往右扫描，它是第一个遇到的 greater value。

👉 面试回答

对 next greater element，我维护一个 decreasing stack，里面存 indexes。

Stack 中的元素都是还没找到 next greater 的元素。

当当前 value 大于 stack top 对应的 value 时，当前 value 就是那个 index 的 next greater element。

我持续 pop 并填答案，直到 stack 恢复 decreasing order。

7️⃣ Next Smaller Element

Problem

对每个元素，找到它右边第一个更小的元素。

nums = [2, 1, 4, 3]
answer = [1, -1, 3, -1]

Stack Invariant

使用 increasing stack 存 unresolved indexes。

stack 存还没有找到 next smaller element 的 indexes
values 从 bottom 到 top 递增

Code

def next_smaller_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] > num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Key Insight

当 current value 小于 stack top：

current value 就是 stack top 的 next smaller element

👉 面试回答

对 next smaller element，我维护一个 increasing stack。

当当前 value 小于 stack top 对应的 value 时，它就是那个 index 的 next smaller element。

然后 pop 这个 index，继续 resolve 更早的 unresolved elements。

8️⃣ Previous Greater Element

Problem

对每个元素，找到左边最近的更大元素。

nums = [2, 1, 4, 3]
answer = [-1, 2, -1, 4]

Code

def previous_greater_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Stack Invariant

维护 decreasing stack。

在 push 当前 index 前：

stack top 就是左边最近的 greater element

👉 面试回答

对 previous greater element，我从左到右扫描，并维护 decreasing stack。

处理当前 value 前，我先 pop 掉所有小于等于当前 value 的元素，因为它们不可能成为当前或未来元素的 previous greater。

如果 stack 不为空， stack top 就是最近的 greater element。

9️⃣ Previous Smaller Element

Problem

对每个元素，找到左边最近的更小元素。

nums = [2, 1, 4, 3]
answer = [-1, -1, 1, 1]

Code

def previous_smaller_element(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Stack Invariant

维护 increasing stack。

在 push 当前 index 前：

stack top 就是左边最近的 smaller element

👉 面试回答

对 previous smaller element，我维护 increasing stack。

我先 pop 掉大于等于当前 value 的元素。

pop 完之后，如果 stack 不为空， stack top 就是左边最近的 smaller element。

🔟 Strict vs Non-Strict Comparison

为什么重要？

Duplicate values 会让比较条件非常关键：

<
<=
>
>=

Example:

nums = [2, 2, 2]

根据题目需求，equal values 可能需要：

保留在 stack 中
或者
从 stack 中 pop 掉

Common Choices

Previous greater：

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

Previous greater or equal：

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

Previous smaller：

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

Previous smaller or equal：

while stack and nums[stack[-1]] > nums[i]:
    stack.pop()

Senior-Level Rule

先定义清楚你要的 boundary：

strictly greater?
greater or equal?
strictly smaller?
smaller or equal?

👉 面试回答

Duplicate handling 是 monotonic stack 里最容易出错的地方之一。

我会根据题目需要的是 strict boundary 还是 non-strict boundary，决定 equal values 是否要 pop。

对 contribution-counting 题，我经常一边用 strict comparison，另一边用 non-strict comparison，这样可以避免 duplicate double counting。

1️⃣1️⃣ Daily Temperatures

Problem

对每一天，返回还要等几天才会遇到更高温度。

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer       = [1, 1, 4, 2, 1, 1, 0, 0]

Pattern

这是 next greater element 的 distance 版本。

next warmer temperature = next greater element
answer = next_index - current_index

Code

def daily_temperatures(temperatures):
    result = [0] * len(temperatures)
    stack = []

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            previous_index = stack.pop()
            result[previous_index] = i - previous_index

        stack.append(i)

    return result

👉 面试回答

Daily Temperatures 是 next greater element 问题。

Stack 存还没找到 warmer future day 的 indexes。

当当前温度高于 stack top 那天的温度时，当前 day 就 resolve 那一天。

答案就是两个 index 的距离。

1️⃣2️⃣ Next Greater Element II - Circular Array

Problem

在 circular array 中找 next greater element。

nums = [1, 2, 1]
answer = [2, -1, 2]

Key Idea

遍历数组两次。

for i in range(2 * n):
    index = i % n

第二轮模拟 circular behavior。

Code

def next_greater_elements_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        index = i % n

        while stack and nums[stack[-1]] < nums[index]:
            prev_index = stack.pop()
            result[prev_index] = nums[index]

        if i < n:
            stack.append(index)

    return result

为什么只在第一轮 Push？

First pass: create unresolved candidates
Second pass: only resolve candidates

如果第二轮还 push，会产生 duplicate indexes。

👉 面试回答

对 circular next greater element，我通过遍历两次数组来模拟环形结构。

使用 i % n 映射回原数组 index。

第一轮 push indexes，第二轮只用来 resolve 剩下的 unresolved indexes。

这样可以避免重复 push 同一个 index。

1️⃣3️⃣ Online Stock Span

Problem

对每个 stock price，返回连续多少天，包括今天，价格都小于等于今天价格。

prices = [100, 80, 60, 70, 60, 75, 85]
span   = [1,   1,  1,  2,  1,  4,  6]

Code

class StockSpanner:

    def __init__(self):
        self.stack = []

    def next(self, price):
        span = 1

        while self.stack and self.stack[-1][0] <= price:
            previous_price, previous_span = self.stack.pop()
            span += previous_span

        self.stack.append((price, span))
        return span

Stack Invariant

Stack 中 prices 保持 decreasing order。

每一项存：

(price, compressed_span)

👉 面试回答

Stock Span 使用 monotonic decreasing stack。

Stack 中每一项存 price 和 compressed span。

当当前 price 大于等于 stack top price 时，我 pop stack top，并把它的 span 合并到当前 span。

这样每次 next 操作是 amortized O(1)。

1️⃣4️⃣ Largest Rectangle in Histogram

Problem

给定 bar heights，找最大矩形面积。

heights = [2, 1, 5, 6, 2, 3]
answer = 10

Key Insight

对每个 bar，需要找到：

left first smaller bar
right first smaller bar

然后：

width = right_smaller_index - left_smaller_index - 1
area = height * width

Code

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    extended = heights + [0]

    for i, height in enumerate(extended):
        while stack and extended[stack[-1]] > height:
            h = extended[stack.pop()]
            left_smaller_index = stack[-1] if stack else -1
            width = i - left_smaller_index - 1
            max_area = max(max_area, h * width)

        stack.append(i)

    return max_area

Pop 的时候发生了什么？

当一个 bar 被 pop：

current index = 右边第一个 smaller element
new stack top = 左边第一个 smaller element

所以可以计算以被 pop 的 bar 作为最低高度的最大矩形。

👉 面试回答

Largest Rectangle in Histogram 使用 monotonic increasing stack。

Stack 存 increasing heights 的 indexes。

当当前 height 小于 stack top 的 height 时，被 pop 的 bar 找到了右边第一个 smaller boundary。

pop 后新的 stack top 是左边第一个 smaller boundary。

这样就可以计算以被 pop bar 作为 limiting height 的最大矩形。

1️⃣5️⃣ 为什么加 Sentinel Value？

没有 Sentinel 的问题

数组结束时，stack 中可能还有没有处理的 bars。

Example:

heights = [1, 2, 3, 4]

右边没有 smaller bar 出现。

加 Zero

extended = heights + [0]

最后的 zero 会强制 pop 掉 stack 中剩下的所有 bars。

Alternative

也可以在 loop 后清理 stack：

while stack:
    process remaining bars

但 sentinel 更简洁。

👉 面试回答

在 histogram 问题中，我通常会在 heights 末尾加一个 sentinel zero。

这个 zero 会强制 stack 中剩余的 bars 全部被 pop 并处理。

这样可以避免单独写 cleanup loop，逻辑更统一。

1️⃣6️⃣ Maximal Rectangle

Problem

给定 binary matrix，找只包含 1 的最大矩形。

Key Idea

把每一行转化成 histogram。

height[c] = 到当前行为止，column c 上连续 1 的数量

然后运行：

largest rectangle in histogram

Code

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    heights = [0] * cols
    best = 0

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == "1":
                heights[c] += 1
            else:
                heights[c] = 0

        best = max(best, largest_rectangle_area(heights))

    return best

👉 面试回答

Maximal Rectangle 可以把 2D matrix 问题转化成多个 histogram 问题。

对每一行，把它看成 histogram 的底部。

每个 column height 表示到当前行为止连续 1 的数量。

然后对每一行应用 largest rectangle in histogram 算法。

1️⃣7️⃣ Sum of Subarray Minimums

Problem

给定数组，返回所有 subarray minimum value 的总和。

arr = [3, 1, 2, 4]
answer = 17

Contribution Thinking

不要枚举所有 subarrays，而是问：

对于每个 arr[i]，
有多少个 subarrays 会把 arr[i] 当成 minimum？

如果：

left_count = 左边界选择数量
right_count = 右边界选择数量

那么 contribution 是：

arr[i] * left_count * right_count

Boundary Choice

为了避免 duplicates double counting，使用 asymmetric comparisons：

previous strictly smaller
next smaller or equal

或者：

previous smaller or equal
next strictly smaller

只要保持一致即可。

Code

def sum_subarray_mins(arr):
    mod = 10 ** 9 + 7
    n = len(arr)

    prev_less = [-1] * n
    next_less_equal = [n] * n

    stack = []

    # previous strictly less
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()

        if stack:
            prev_less[i] = stack[-1]

        stack.append(i)

    stack = []

    # next less or equal
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()

        if stack:
            next_less_equal[i] = stack[-1]

        stack.append(i)

    result = 0

    for i in range(n):
        left_count = i - prev_less[i]
        right_count = next_less_equal[i] - i
        result += arr[i] * left_count * right_count

    return result % mod

👉 面试回答

Sum of Subarray Minimums 是 monotonic stack 的 contribution counting 问题。

我不会枚举所有 subarrays。

我会计算每个元素作为 minimum 时能覆盖多少个 subarrays。

对每个 index，找到 previous smaller boundary 和 next smaller boundary。

左边可选数量乘以右边可选数量，就是这个元素作为 minimum 的 subarray 数量。

为了处理 duplicates，一边用 strict comparison，另一边用 non-strict comparison。

1️⃣8️⃣ Sum of Subarray Ranges

Problem

对每个 subarray：

range = max - min

返回所有 subarray ranges 的总和。

Key Idea

sum of ranges
= sum of subarray maximums - sum of subarray minimums

用 monotonic stack 做两次 contribution：

一次计算每个元素作为 maximum 的贡献
一次计算每个元素作为 minimum 的贡献

Contribution Formula

对每个元素：

contribution = value * left_count * right_count

作为 maximum：

find previous greater and next greater boundary

作为 minimum：

find previous smaller and next smaller boundary

👉 面试回答

Sum of Subarray Ranges 可以用 contribution counting。

一个 subarray 的 range 等于 maximum 减 minimum。

所以我分别计算每个元素作为 maximum 的总贡献，再减去它作为 minimum 的总贡献。

Monotonic stack 可以帮助我们找到每个元素作为 max 或 min 时能扩展的左右边界。

1️⃣9️⃣ Remove K Digits

Problem

从数字字符串中移除 k 位，使剩下的数字最小。

num = "1432219", k = 3
answer = "1219"

Key Idea

维护 increasing stack of digits。

如果当前 digit 比 stack top 小：

while k > 0:
    pop larger previous digit

因为移除更靠前的较大数字，可以让整体数字更小。

Code

def remove_k_digits(num, k):
    stack = []

    for digit in num:
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1

        stack.append(digit)

    while k > 0:
        stack.pop()
        k -= 1

    result = "".join(stack).lstrip("0")

    return result if result else "0"

👉 面试回答

Remove K Digits 使用 monotonic increasing stack。

为了让数字尽可能小，当当前 digit 小于前一个 digit 时，如果还有删除次数，我会删除前一个更大的 digit。

处理完所有 digits 后，如果 k 还有剩余，就从末尾继续删除。

最后去掉 leading zeros。

2️⃣0️⃣ Trapping Rain Water With Stack

Problem

给定 bar heights，计算可以接多少雨水。

height = [0,1,0,2,1,0,1,3,2,1,2,1]
answer = 6

Stack Idea

Stack 存 bar indexes。

当 current bar 高于 stack top：

可能找到了 right boundary

Pop 出 valley bottom，然后计算 water：

bounded_height = min(left_boundary_height, right_boundary_height) - bottom_height
width = right_index - left_index - 1
water = bounded_height * width

Code

def trap(height):
    stack = []
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()

            if not stack:
                break

            left = stack[-1]
            width = i - left - 1
            bounded_height = min(height[left], h) - height[bottom]
            water += width * bounded_height

        stack.append(i)

    return water

👉 面试回答

Trapping Rain Water 可以用 monotonic stack。

Stack 存 bar indexes。

当当前 bar 高于 stack top 时，被 pop 的 bar 可以作为 valley bottom。

如果 stack 中还有 left boundary，就用 left boundary 和 current bar 作为左右边界，计算能接的 water。

2️⃣1️⃣ 什么时候 Monotonic Stack 适用？

Good Fit

当题目问：

nearest greater element
nearest smaller element
next greater element
previous greater element
next smaller element
previous smaller element
span until greater/smaller
first boundary where condition breaks
contribution as minimum or maximum

Problem Signals

看到这些关键词时想到 monotonic stack：

next greater
next warmer
previous smaller
nearest smaller
span
histogram
rectangle
subarray minimum
subarray maximum
remove digits
first smaller boundary

👉 面试回答

当题目需要找 nearest greater 或 nearest smaller element 时，我会优先考虑 monotonic stack。

如果每个元素都需要找左右边界，或者需要计算每个元素作为 minimum / maximum 的贡献， monotonic stack 也非常适合。

2️⃣2️⃣ 什么时候 Monotonic Stack 不适用？

Not Good Fit

Monotonic stack 通常不适合：

condition 不是基于 nearest greater/smaller boundary
需要 global sorting
需要 arbitrary range query
需要 shortest path
更适合 heap、binary search 或 DP 的问题

Better Alternatives

Problem Type	Better Pattern
Need global minimum repeatedly	Heap
Need range sum query	Prefix Sum
Need range max/min query	Segment Tree / Sparse Table
Need shortest path	BFS / Dijkstra
Need sorted order globally	Sorting / Binary Search
Need optimal substructure	Dynamic Programming

👉 面试回答

Monotonic stack 是一个专门解决 nearest boundary 的 pattern。

如果问题需要 global ordering、任意 range query、shortest path，或者 optimal substructure，那可能应该考虑 heap、segment tree、BFS、DP 等其他模式。

2️⃣3️⃣ 常见 Edge Cases

Empty Input

nums = []

Single Element

nums = [5]

Strictly Increasing Array

[1, 2, 3, 4]

在 next greater 问题中会触发很多 pop。

Strictly Decreasing Array

[4, 3, 2, 1]

可能会留下很多 unresolved elements。

Duplicates

[2, 2, 2]

必须明确 strict vs non-strict comparison。

Circular Arrays

需要 two passes 或 modulo indexing。

👉 面试回答

常见 edge cases 包括 empty input、 single element、 strictly increasing array、 strictly decreasing array、 duplicates、以及 circular array。

Duplicates 特别重要，因为 strict 和 non-strict comparison 会改变结果。

2️⃣4️⃣ Complexity Analysis

Time Complexity

大多数 monotonic stack 算法是：

O(n)

因为每个元素最多：

push once
pop once

Space Complexity

通常是：

O(n)

用于 stack 和 result array。

Amortized Analysis

虽然代码看起来像：

for i in range(n):
    while stack:
        stack.pop()

但不是 O(n²)。

因为每个元素在全局最多只会 pop 一次。

👉 面试回答

Monotonic stack 通常是 O(n) time 和 O(n) space。

重点是 amortized analysis。

虽然 for loop 里面可能有 while loop，但是每个元素最多 push 一次、pop 一次，所以总 stack operations 是 linear。

2️⃣5️⃣ 常见错误

Mistake 1: Stack Direction 错误

该用 decreasing stack，却用了 increasing stack。

Mistake 2: 该存 Index 却存 Value

如果题目要 distance、width 或 position，通常要存 index。

Mistake 3: Duplicate Handling 错误

使用：

但题目需要：

<=

或者反过来。

Mistake 4: 忘记 Sentinel

Histogram 问题经常需要：

heights + [0]

或者 cleanup loop。

Mistake 5: 没解释 Amortized O(n)

面试官可能会问：

为什么这不是 O(n²)？

Mistake 6: 混淆 Next 和 Previous Boundary

Next boundary 通常在 pop 时被 resolve。

Previous boundary 通常在 push 前从 stack top 读取。

👉 面试回答

常见错误包括： monotonic direction 搞反、需要 index 却只存 value、 duplicate comparison 处理错误、忘记 sentinel、以及混淆 next-boundary 和 previous-boundary 的逻辑。

我会通过先定义 stack invariant 来避免这些问题。

2️⃣6️⃣ 标准模板

Next Greater Element Template

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Next Smaller Element Template

def next_smaller(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] > num:
            index = stack.pop()
            result[index] = num

        stack.append(i)

    return result

Previous Greater Element Template

def previous_greater(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Previous Smaller Element Template

def previous_smaller(nums):
    result = [-1] * len(nums)
    stack = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] >= num:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

Circular Next Greater Template

def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        index = i % n

        while stack and nums[stack[-1]] < nums[index]:
            prev = stack.pop()
            result[prev] = nums[index]

        if i < n:
            stack.append(index)

    return result

Histogram Template

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    extended = heights + [0]

    for i, height in enumerate(extended):
        while stack and extended[stack[-1]] > height:
            h = extended[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, h * width)

        stack.append(i)

    return max_area

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Monotonic stack 是一种维护 increasing 或 decreasing order 的 stack。

它主要用于 nearest greater 或 nearest smaller boundary 问题。

Stack 通常存 unresolved indexes，也就是那些还没有找到 next greater、next smaller 或 boundary 的元素。

当当前元素破坏 monotonic invariant 时，我们会 pop stack 中的元素，并为这些元素确定答案。

对 next greater element，我维护 decreasing stack。当当前 value 大于 stack top 对应的 value 时，当前 value 就是被 pop index 的 next greater element。

对 next smaller element，我维护 increasing stack。当当前 value 小于 stack top 时，它就 resolve next smaller answer。

对 previous greater 或 previous smaller，我通常先 pop 掉 invalid candidates。然后 stack top 就是最近的 valid previous boundary。

一个关键细节是 duplicate handling。 Strict 和 non-strict comparison 的选择非常重要。对 contribution-counting 题，比如 sum of subarray minimums，我会一边使用 strict comparison，另一边使用 non-strict comparison，来避免 duplicate double counting。

Largest Rectangle in Histogram 是经典 monotonic stack 题。我维护 increasing stack of bar indexes。当当前 bar 更矮时，被 pop 的 bar 找到了 right smaller boundary。新的 stack top 提供 left smaller boundary。这样可以计算以被 pop bar 作为最低高度的最大矩形。

Monotonic stack 也适用于 circular array，可以通过遍历两次数组来模拟环。

它还适用于 contribution problems，通过计算每个元素作为 minimum 或 maximum 时能扩展的左右边界，得到每个元素的总贡献。

复杂度通常是 O(n) time 和 O(n) space。虽然代码中经常有 for loop 里的 while loop，但每个元素最多 push 一次、pop 一次，所以总 stack operations 是 linear。

高级工程师解释 monotonic stack 时，我会明确说明： stack 里存什么，它是 increasing 还是 decreasing，它维护什么 invariant，什么条件触发 pop， pop 的时候解决了什么答案，以及 duplicates 如何处理。

⭐ Final Insight

Monotonic Stack 的核心不是“背 next greater 模板”。

它的核心是维护一组单调有序的 unresolved candidates。

Senior-level 的重点是：

stack 是 increasing 还是 decreasing， stack 存 index 还是 value， pop 时解决了什么问题， stack top 代表什么 boundary， duplicates 用 strict 还是 non-strict comparison，以及为什么整体是 amortized O(n)。

能讲清楚这些， Monotonic Stack 就是一种处理 nearest boundary 和 contribution counting 的高级算法模式。