Farthest Candidate Stack

When To Use

Use this when you need the farthest valid index, not the nearest greater/smaller index.

Template

build decreasing prefix candidate stack
 
for r from n - 1 down to 0:
    while stack not empty and stack.back satisfies with r:
        update answer
        pop back

You do not pop while building; early candidates are valuable because they are farther away.

Problems

Maximum Width Ramp

Problem: maximize j - i with i < j and nums[i] <= nums[j].

Pattern: decreasing prefix stack, then scan from the right.

Applied pseudocode:

for i = 0; i < n; i++:
    if stack empty or nums[i] < nums[stack.back]:
        stack.push_back(i)
 
for j = n - 1 down to 0:
    while stack not empty and nums[stack.back] <= nums[j]:
        ans = max(ans, j - stack.back)
        stack.pop_back()

Longest Well Performing Interval

Problem: longest interval with more tiring days than non-tiring days.

Pattern: transform to prefix scores, then find farthest smaller prefix.