Tallest Stack After Each Falling Block
Square blocks drop one by one onto a number line. Each lands on top of whatever it overlaps. After every drop, report the current height of the tallest stack anywhere.
Problem
Given positions[i] = [left_i, sideLength_i], the i-th square occupies [left_i, left_i + sideLength_i) and falls down until it rests on the floor or on top of an earlier square it overlaps. After each square lands, record the maximum height of any stack so far. Return the list of these running maxima.
Input
An array positions of [left, sideLength] pairs in drop order.
Output
An array where the i-th entry is the tallest stack height after the i-th square lands.
Constraints
- 1 <= positions.length <= 1000
- 1 <= left_i <= 10^8
- 1 <= sideLength_i <= 10^6
- Squares are half-open horizontally: [left, left + side).
Examples
Example 1
Input
positions = [[1,2],[2,3],[6,1]]
Output
[2,5,5]
First square rests at height 2; second overlaps it, landing on top → 5; third is isolated at height 1.
Example 2
Input
positions = [[100,100],[200,100]]
Output
[100,100]
Touching at x=200 does not overlap; both sit on the floor.