Long Queue
EasyP3Coding
People join a queue in groups. Inside one group the members stand in non-decreasing order of height (equal heights are allowed). Groups stand one behind another, and nothing tells you where one group ends.
Given the final line-up heights, return the minimum number of groups that could have produced it. An empty queue needs 0 groups.
Example 1
- Input
- heights = [1,2,3,2,3,1]
- Output
- 3
- Why
- Groups: [1,2,3], [2,3], [1].
Example 2
- Input
- heights = [1,2,3]
- Output
- 1
Example 3
- Input
- heights = []
- Output
- 0
Constraints
- 0 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^9
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.