arrays - 找到最小数量需要的喷泉数量

Question

从1到n有一个线性花园。每个点都有一个喷泉。给定数组 a[n] 告诉有关喷泉的信息，其范围是从喷泉左侧的 max(i-a[i],1) 到喷泉右侧的 min(i+a[i],n)。找到最小数量需要激活的喷泉才能覆盖整个花园。
例如，如果 n=3 并且 a={1,2,1} 则第二个喷泉的范围是 1 到 3。所以只需要 1 个喷泉。这里 1 处的喷泉的范围是 1 到 2，
2 处的喷泉范围为 1 到 3，而 3 处的喷泉范围为 2 到 3
所以只要启动喷泉2就足以覆盖整个花园。

Answer 1

我认为您正在寻找 O(n) 时间和 O(n) 空间之外的解决方案。

创建区间数组来存储当前索引可以覆盖的最右边的范围。

public int findMinActivatedFountain(int[] arr, int n) {
        int[] interval = new int[n];
        int count = 1;

        // At each index we'll store the max right possible from this index.
        for (int i = 1; i <= n; i++) {
            int left = Math.max(i - arr[i - 1], 1);
            int right = Math.min(i + arr[i - 1], n);

            interval[left - 1] = right;
        }

        int right = interval[0];
        int currMax = right;
        for (int i = 1; i < n; i++) {
            currMax = Math.max(currMax, interval[i]);

            // If the last fountain can cover only this point, then update with next fountain.
            if (i == right) {
                count++;
                right = currMax;
            }
        }
        return count;
    }