找出可以在山峰上设置的最大旗帜数量

Question

我处理了下面提供的 Codility 问题，

给出一个由N个整数组成的非空数组A

峰是一个数组元素，它比它的邻居大。更准确地说，it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].

For example, the following array A:

    A[0] = 1
    A[1] = 5
    A[2] = 3
    A[3] = 4
    A[4] = 3
    A[5] = 4
    A[6] = 1
    A[7] = 2
    A[8] = 3
    A[9] = 4
    A[10] = 6
    A[11] = 2

恰好有四个峰：元素 1、3、5 和 10。

您要去一系列山脉旅行，其相对高度由数组 A 表示，如下图所示。你必须选择你应该带多少旗帜。目标是根据特定规则在山峰上设置最大数量的标志。

只能在峰上设置标志。另外，如果取K个flags，那么任意两个flags之间的距离应该大于等于K。索引P和Q之间的距离是绝对值|P − Q|。

例如，给定上面数组 A 表示的山脉，其中 N = 12，如果您采用：

两个flag，可以设置在1峰和5峰；三个标志，你可以将它们设置在 1、5 和 10 峰上；四个标志，您只能在峰 1、5 和 10 上设置三个标志。因此，在这种情况下，您最多可以设置三个标志。

写一个函数：

class Solution { public int solution(int[] A); }

给定一个包含 N 个整数的非空数组 A，returns 是可以在数组的顶点上设置的最大标志数。

例如下面的数组A：

A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2

函数应该 return 3，如上所述。

假设：

N is an integer within the range [1..400,000];
each element of array A is an integer within the range [0..1,000,000,000].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

我完成了下面提供的解决方案，

public static int solution(int[] A) {

        int N = A.length;

        /*
         * P =  [1, 1, 3, 3, 5, 5, 10, 10, 10, 10, 10, -1]
         * */
        int[] P = nextPeak(A);

        int i = 1;
        int result = 0;

        while ((i - 1) * i <= N) {

            int index = 0;
            int flags = 0;

            while (index < N && flags < i) {

                /*
                 * P =  [1, 1, 3, 3, 5, 5, 10, 10, 10, 10, 10, -1]
                 * */
                index = P[index];

                if (index == -1) {
                    break;
                }

                flags += 1;
                index += i;
            }

            /*
             * maximize the number of flags for the whole segment
             * */
            result = Math.max(result, flags);
            i++;
        }

        return result;
    }


    /*
     * A = [1, 1, 3, 3, 5, 5, 10, 10, 10, 10, 10, -1]
     * */
    public static int[] nextPeak(int[] P) {

        int N = P.length;

        ArrayList<Integer> peaks = new ArrayList<Integer>();

        for (int i = 1; i < P.length - 1; i++) {

            if (P[i] > P[i - 1] && P[i] > P[i + 1]) {
                peaks.add(i);
            }
        }

        int[] A = new int[N];
        A[N - 1] = -1;


        for (int i = N - 2; i >= 0; i--) {

            if (peaks.contains(i)) {
                A[i] = i;
            } else {
                A[i] = A[i + 1];
            }
        }

        return A;
    }

总的来说，我理解计算但看不出我们在哪里满足条件if you take K flags, then the distance between any two flags should be greater than or equal to K。

我想这是在 (i-1)*i <= N 的 while 条件内，但无法正确理解它。有好心人给我解释一下吗？

Answer 1

您的答案是 index += i; 结合 while 循环中的条件 flags < i。他们逆向求解：一次走 K 步，最多插入 K 个标志。

找出可以在山峰上设置的最大旗帜数量

Find the maximum number of flags that can be set on mountain peaks

java

arrays

approximation