The next one taller than this
A shelf-planning tool walks a row of stacked crates and, for each one, reports the height of the first crate to its right that stands taller.
- Look only to the right of each crate.
- Report the height of the first taller crate, not how far away it is.
- A crate with nothing taller to its right reports -1.
- Equal height is not taller.
NextTaller(heights: list<int>) → list<int>
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public List<int> NextTaller(List<int> heights) {
}Worked examples
| Call | Result |
|---|---|
NextTaller(new List<int> { 2, 1, 2, 4, 3 }) | new List<int> { 4, 2, 4, -1, -1 } |
NextTaller(new List<int> { 5, 4, 3 }) | new List<int> { -1, -1, -1 } |
NextTaller(new List<int> { 1, 2, 3 }) | new List<int> { 2, 3, -1 } |
NextTaller(new List<int> { 2, 2, 2 }) | new List<int> { -1, -1, -1 } |
Hint
Walk once, keeping a stack of the crates still waiting for an answer. Each new height settles every waiting crate shorter than it.
Reference solution in C#
public List<int> NextTaller(List<int> heights) {
var answer = new List<int>();
for (int i = 0; i < heights.Count; i++) answer.Add(-1);
var waiting = new Stack<int>();
for (int i = 0; i < heights.Count; i++) {
while (waiting.Count > 0 && heights[waiting.Peek()] < heights[i]) {
answer[waiting.Pop()] = heights[i];
}
waiting.Push(i);
}
return answer;
}