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>
Java 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
List<Integer> nextTaller(List<Integer> heights) {
}Worked examples
| Call | Result |
|---|---|
nextTaller(Main.<Integer>ls(2, 1, 2, 4, 3)) | Main.<Integer>ls(4, 2, 4, -1, -1) |
nextTaller(Main.<Integer>ls(5, 4, 3)) | Main.<Integer>ls(-1, -1, -1) |
nextTaller(Main.<Integer>ls(1, 2, 3)) | Main.<Integer>ls(2, 3, -1) |
nextTaller(Main.<Integer>ls(2, 2, 2)) | Main.<Integer>ls(-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 Java
List<Integer> nextTaller(List<Integer> heights) {
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < heights.size(); i++) answer.add(-1);
Deque<Integer> waiting = new ArrayDeque<>();
for (int i = 0; i < heights.size(); i++) {
while (!waiting.isEmpty() && heights.get(waiting.peek()) < heights.get(i)) {
answer.set(waiting.pop(), heights.get(i));
}
waiting.push(i);
}
return answer;
}