990. Stacking Squares
Square tiles are dropped one by one onto a very long shelf. The i-th tile is squares[i] = [left, side]: it occupies the horizontal range from left to left + side and has height side. It falls straight down until its bottom rests on the floor or on the top of an earlier tile that it overlaps over a range of positive width. Tiles that merely touch along a vertical edge do not support each other. Once it lands, a tile never moves.
Return an array whose i-th element is the height of the tallest stack on the shelf right after the i-th tile has landed.
Example 1
- Input:
- squares = [[2,3],[6,2],[4,4],[1,1]]
- Output:
- [3,3,7,7]
- Explanation:
The first tile (x 2..5) has height 3 and the second (x 6..8) has height 2. The third tile spans x 4..8, lands on the taller overlapped tile (height 3) and reaches height 7. The last tile at x 1..2 only touches the first one at x = 2, so it lands on the floor; the tallest stack stays 7.
Example 2
- Input:
- squares = [[0,5],[0,2],[3,3],[1,1]]
- Output:
- [5,7,8,8]
- Explanation:
Tile one has height 5; tile two lands on it, giving 7. Tile three spans x 3..6 and rests on tile one (top 5), reaching 8. The last tile lands on tile two (top 7) for a top of 8, so the tallest stack is 5, 7, 8, 8 after the four drops.
Constraints
- 1 ≤ squares.length ≤ 2 * 104
- 0 ≤ left ≤ 109 and 1 ≤ side ≤ 104
- left + side ≤ 2 * 109 - 1, and every answer fits in a 32-bit integer
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n log n) amortised
- Space
- O(n)