```
= []
stack
for item in [1, 2, 5, 3, 7, 4]:
push(stack, item)print(f"After push {item}:", stack)
```

```
After push 1: [1]
After push 2: [1, 2]
After push 5: [1, 2, 5]
After push 3: [1, 2, 3]
After push 7: [1, 2, 3, 7]
After push 4: [1, 2, 3, 4]
```

Find the largest difference between two indices with increasing value in their corresponding array values.

Author

Published

October 10, 2024

The full problem statement may be found on leetcode.

The phrasing of the problem is obfuscatory - the objective is to look for a pair of indices \(i, j\) for an array \(a: S\subset \mathbb{N} \to \mathbb{N}\) such that \(i \lt j\) and \(\phi(i) \leq \phi(j)\) and \(j - i\) is maximal.

This is actually a rather tricky problem - I had never encountered the monotonic stack approach until today.

A monotonic stack is a stack where elements are ordered monotonically. *wow! What a shock that is.* To make this happen, when an element that does not obey the ordering is pushed, elements are removed from the top until the new element can be pushed and maintain monotonicity.

```
Initial stack: 1 -> 2 -> 5
Stack when 3 is pushed: 1 -> 2 -> 3
Stack when 7 is pushed: 1 -> 2 -> 3 -> 7
Stack when 4 is pushed: 1 -> 2 -> 3 -> 4
```

The following example will push elements onto a stack with monotonic rules:

```
def push(stack: list[int], value: int, *, _top: int | None = None) -> int:
top = _top or (len(stack) - 1)
while stack and stack[top] > value:
stack.pop()
top -= 1
stack.append(value)
return top
```

and we can reproduce the above by running the following code:

```
class Solution:
def maxWidthRamp(self, nums: list[int]) -> int:
n = len(nums)
stack: list[int] = []
for index in range(n):
num = nums[index]
if not stack or nums[stack[-1]] > num:
stack.append(index)
max_width = 0
for k in range(n - 1, -1, -1):
while stack and nums[stack[-1]] <= nums[k]:
max_width = max(max_width, k - stack.pop())
return max_width
```