Beacon stretches
MediumOnline Assessment
Count the stretches of a tower row that have exactly one tallest tower.
A coastal road has a row of watchtowers. The string heights has one digit character per tower, in road order, and each digit is that tower's height ("0" to "9"). A stretch is a non-empty run of consecutive towers. A stretch is guided when its tallest height belongs to exactly one tower in the stretch: if two or more towers share the greatest height, the stretch is not guided.
Stretches are told apart by where they start and end, so two stretches with the same heights at different places are counted separately. A stretch of a single tower is always guided.
Input: heights, a string of digit characters.
Output: an integer, the number of guided stretches. An empty string has no stretches, so return 0.
The road can be very long, so checking every stretch one by one will be too slow.
Example 1
- Input:
- ["55"]
- Output:
- 2
- Explanation
- Both towers have height 5. The single-tower stretches
5and5are guided, but the stretch55has two tallest towers, so it is not. The answer is 2.
Example 2
- Input:
- ["3113"]
- Output:
- 8
- Explanation
- The four single towers are guided. Among longer stretches,
31,13,311and113each have one tallest tower, while11and the whole row3113(two towers of height 3) do not. That makes 4 + 2 + 2 = 8.
Example 3
- Input:
- ["2403"]
- Output:
- 10
- Explanation
- The heights 2, 4, 0, 3 are all different, so no stretch can have a tie for tallest. All 10 stretches (4 + 3 + 2 + 1) are guided.
Constraints
0 <= heights.length <= 40,000- every character of
heightsis a digit from"0"to"9" - the answer fits comfortably in a 64-bit integer