Minimum Fence Painting Operations
A fence is made of n adjacent vertical boards. Board i has width 1 and height heights[i].
You have a brush of width 1 and may perform only these two types of painting operations:
- Vertical stroke: paint one entire board from bottom to top in a single operation.
- Horizontal stroke: paint exactly one unit of height across a contiguous segment of adjacent boards. A horizontal stroke may cover only portions of boards that still need paint.
Return the minimum number of operations required to paint the entire fence.
Complete the function minPaintOperations in the editor below.
minPaintOperations has the following parameter:
int[] heights: the heights of the boards
Returns
int: the minimum number of painting operations.
heights = [2, 2, 1, 2, 1] return = 3
Paint one horizontal stroke across all five boards to cover the first unit of height. Then paint a second horizontal stroke across the first two boards. Finally, paint board 4 vertically. The entire fence is painted in 3 operations.
heights = [1, 1, 1, 1] return = 1
A single horizontal stroke across all four boards paints the whole fence.
The source thread did not provide explicit numeric bounds.
heights.length >= 1- Each
heights[i]is a non-negative integer.
public int minPaintOperations(int[] heights) {
// write your code here
}