Gemini

01Minimum 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. Function Description 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.

Constraints

The source thread did not provide explicit numeric bounds.

heights.length ≥ 1
Each heights[i] is a non-negative integer.

解法

分治/贪心。对当前区间 [l, r]，最优策略是要么垂直涂每根 (r-l+1 次)；要么先横涂 min(heights[l..r]) 次，再对水平线之上的剩余部分递归处理被切分的子区间。取两者最小值。时间复杂度 O(n²) 最坏(顺序栈大小)，可优化为 O(n) 用稀疏表，但 n 较小直接递归即可。空间复杂度 O(n) 递归栈。

from typing import List

def minPaintOperations(heights: List[int]) -> int:
    def solve(l: int, r: int, base: int) -> int:
        if l > r:
            return 0
        m = min(heights[l:r + 1])
        # vertical
        vertical = r - l + 1
        # horizontal: paint (m - base) horizontal strokes, then recurse on sub-intervals
        horizontal = m - base
        i = l
        while i <= r:
            if heights[i] == m:
                i += 1
                continue
            j = i
            while j <= r and heights[j] > m:
                j += 1
            horizontal += solve(i, j - 1, m)
            i = j
        return min(vertical, horizontal)

    return solve(0, len(heights) - 1, 0)

class Solution {
    int[] h;

    int minPaintOperations(int[] heights) {
        this.h = heights;
        return solve(0, heights.length - 1, 0);
    }

    private int solve(int l, int r, int base) {
        if (l > r) return 0;
        int m = Integer.MAX_VALUE;
        for (int i = l; i <= r; i++) m = Math.min(m, h[i]);
        int vertical = r - l + 1;
        int horizontal = m - base;
        int i = l;
        while (i <= r) {
            if (h[i] == m) { i++; continue; }
            int j = i;
            while (j <= r && h[j] > m) j++;
            horizontal += solve(i, j - 1, m);
            i = j;
        }
        return Math.min(vertical, horizontal);
    }
}

class Solution {
public:
    int minPaintOperations(vector<int>& heights) {
        return solve(heights, 0, (int)heights.size() - 1, 0);
    }

private:
    int solve(vector<int>& h, int l, int r, int base) {
        if (l > r) return 0;
        int m = INT_MAX;
        for (int i = l; i <= r; i++) m = min(m, h[i]);
        int vertical = r - l + 1;
        int horizontal = m - base;
        int i = l;
        while (i <= r) {
            if (h[i] == m) { i++; continue; }
            int j = i;
            while (j <= r && h[j] > m) j++;
            horizontal += solve(h, i, j - 1, m);
            i = j;
        }
        return min(vertical, horizontal);
    }
};