962. Maximum Width Ramp
Approach
Build a decreasing-value stack of indices left-to-right; scan right-to-left popping while nums[j] >= nums[stack.top].
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Stacks support LIFO (last-in, first-out) operations in O(1). Key patterns: balanced parentheses, next greater element (monotonic stack), function call simulation, and undo/redo. A monotonic stack maintains a strictly increasing or decreasing order to answer range queries efficiently.
A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element violates this order, elements are popped and processed. Use for "next greater / smaller element", histogram area, and stock span problems. Each element is pushed and popped at most once — O(n) overall.
// Approach: Build a decreasing-value stack of indices left-to-right; scan right-to-left popping while nums[j] >= nums[stack.top].
// Time: O(n) Space: O(n)
public class Solution
{
public int MaxWidthRamp(int[] nums)
{
int ans = 0;
Stack<int> stack = new Stack<int>();
for (int i = 0; i < nums.Length; ++i)
{
if (stack.Count == 0 || nums[i] < nums[stack.Peek()])
stack.Push(i);
}
for (int i = nums.Length - 1; i > ans; --i)
{
while (stack.Count > 0 && nums[i] >= nums[stack.Peek()])
ans = Math.Max(ans, i - stack.Pop());
}
return ans;
}
}