How it works
The next-greater problem asks for the first later value strictly greater than each element. A monotonic stack holds positions whose answers have not yet been found. When a new value exceeds the stack's top value, that new value resolves the pending position and the algorithm continues checking earlier unresolved positions.
Four resolves both one and two in the sample. Three cannot resolve four, and no later value resolves either of the last two positions. The nullable result array represents those missing answers explicitly, avoiding a sentinel such as negative one that could also be a legitimate next-greater value in another input.
Indices preserve output location even when values repeat. Storing only values would lose the direct connection to the original array positions. The pending values remain nonincreasing from the bottom toward the top under this strict comparison, which is why one incoming value can resolve several pending positions efficiently.
Although the code contains a while loop inside a for loop, each index is pushed once and popped at most once. The total stack work is therefore linear across the whole input rather than quadratic. This is an amortized accounting argument: count each position's lifetime, not the apparent nesting alone.
Practice with an increasing sequence, a decreasing sequence, repeated equal values, and negative numbers. Explain why equal values do not resolve one another under the strictly-greater contract. Change the comparison only after deciding whether greater-or-equal is actually the desired problem.
Finally, compare the result with a simple nested-loop reference that scans rightward from each position. Use small hand-written arrays to verify both values and missing cases. The optimized method is easier to trust when its unresolved-stack invariant and its one-push-one-pop cost argument are stated alongside tests of the precise strictness boundary.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
int[] values = { 2, 1, 4, 3 };
int?[] next = new int?[values.Length];
var pending = new Stack<int>();
for (int index = 0; index < values.Length; index++) {
while (pending.Count > 0 && values[pending.Peek()] < values[index]) next[pending.Pop()] = values[index];
pending.Push(index);
}
Console.WriteLine(string.Join(",", next.Select(value => value?.ToString(CultureInfo.InvariantCulture) ?? "none")));
Expected output
4,4,none,none
Store unresolved indices, not only values, so each answer can be written to its original position.