965. Layered Increments
A mural wall is divided into n vertical strips, every strip starting at paint height 0. In one stroke the painter picks a contiguous run of strips and raises each strip in that run by exactly 1; a stroke can never skip a strip in the middle of its run, and heights can never be lowered. The array target (0-indexed) gives the height that strip i must have at the end.
Return the minimum number of strokes needed to produce exactly target. If every entry is 0 the answer is 0. The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- target = [2,5,3,4]
- Output:
- 6
- Explanation:
The first strip needs 2 strokes, then rises of 3 (2 to 5) and 1 (3 to 4) each need fresh strokes, giving 2 + 3 + 1 = 6.
Example 2
- Input:
- target = [4,4,4]
- Output:
- 4
- Explanation:
One stroke over all three strips, repeated 4 times, reaches height 4 everywhere.
Example 3
- Input:
- target = [3,0,3]
- Output:
- 6
- Explanation:
The zero strip splits the wall into two separate parts, each needing 3 strokes, so 6 in total.
Constraints
- 1 ≤ target.length ≤ 105
- 0 ≤ target[i] ≤ 104
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 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)