Minimize Fence Painting Operations

Problem Statement

You are tasked with painting a horizontal wooden fence that consists of n adjacent vertical planks. Each plank i has a specific height h[i]. You have a brush that can paint a horizontal segment of any length across one or more adjacent planks, but it can only paint at a single fixed vertical level (height) at a time. Specifically, a single operation allows you to choose a contiguous range [i, j] and a height k, painting all planks in that range up to height k.

However, you can only paint if the planks are currently at height 0 (or were previously painted up to a height less than k). Your goal is to find the minimum number of operations required to paint the entire fence such that every plank i reaches exactly height h[i].

Function Signature

def min_fence_strokes(heights: List[int]) -> int:

Constraints

• 1 <= len(heights) <= 10^5
• 0 <= heights[i] <= 10^9

Examples

Example 1: Input: heights = [1, 2, 1] Output: 2 Explanation: Paint the whole range [0, 2] at height 1 (1 operation), then paint the middle plank at height 2 (1 operation). Total: 2.

Example 2: Input: heights = [3, 1, 2, 2] Output: 3 Explanation: Paint height 3 for index 0, height 1 for index 1, and height 2 for index 2-3.

Edge Cases

• An empty array or an array of all zeros should return 0.
• Planks with identical adjacent heights can be painted in a single stroke.