Crystal Fusion Line
Medium · stack
A workshop lays crystals in a row, from left to right. Each crystal has a grade, a positive whole number, and grades[i] is the grade of the crystal in position i.
Whenever two neighbouring crystals have the same grade g, they fuse into a single crystal of grade g + 1, which takes their place in the row. The new crystal can then fuse with a neighbour of grade g + 1, and so on. This keeps going until no two neighbouring crystals have the same grade.
When more than one pair of neighbours could fuse, the leftmost pair fuses first.
Return the grades of the crystals that remain, from left to right.
Examples
Example 1
Input: grades = [1, 1, 2]
Output: [3]
The two 1s fuse into a 2, giving 2, 2. Those fuse into a 3.
Example 2
Input: grades = [2, 2, 2]
Output: [3, 2]
The leftmost pair fuses first, leaving 3 and the last 2, which are different.
Example 3
Input: grades = [1, 2, 1, 2]
Output: [1, 2, 1, 2]
No two neighbours share a grade, so nothing fuses.
Constraints
- 1 <= len(grades) <= 10^4
- 1 <= grades[i] <= 10^9