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
std::vector<int> nextTaller(std::vector<int> heights) {
}Worked examples
| Call | Result |
|---|---|
nextTaller(std::vector<int>{2, 1, 2, 4, 3}) | std::vector<int>{4, 2, 4, -1, -1} |
nextTaller(std::vector<int>{5, 4, 3}) | std::vector<int>{-1, -1, -1} |
nextTaller(std::vector<int>{1, 2, 3}) | std::vector<int>{2, 3, -1} |
nextTaller(std::vector<int>{2, 2, 2}) | std::vector<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++
std::vector<int> nextTaller(std::vector<int> heights) {
std::vector<int> answer(heights.size(), -1);
std::vector<int> waiting;
for (int i = 0; i < static_cast<int>(heights.size()); i++) {
while (!waiting.empty() && heights[waiting.back()] < heights[i]) {
answer[waiting.back()] = heights[i];
waiting.pop_back();
}
waiting.push_back(i);
}
return answer;
}