实现问题：codility:peaks 在性能测试中的挑战

一分耕耘，一分收获！既然都打开这篇《实现问题：codility:peaks 在性能测试中的挑战》，就坚持看下去，学下去吧！本文主要会给大家讲到等等知识点，如果大家对本文有好的建议或者看到有不足之处，非常欢迎大家积极提出！在后续文章我会继续更新Golang相关的内容，希望对大家都有所帮助！

将数组划分为最大数量的相同大小的块，每个块应包含一个索引 p，使得 a[p - 1] < a[p] > a[p + 1]。

我的解决方案：golang解决方案

但是部分性能测试无故失败，任何人都可以添加一些建议吗？

func Solution(A []int) int {
    peaks := make([]int, 0)
    for i := 1; i < len(A)-1; i++ {
        if A[i] > A[i-1] && A[i] > A[i+1] {
            peaks = append(peaks, i)
        }
    }

    if len(peaks) <= 0 {
        return 0
    }

    maxBlocks := 0

    // we only loop through the possible block sizes which are less than
    // the size of peaks, in other words, we have to ensure at least one
    // peak inside each block 
    for i := 1; i <= len(peaks); i++ {
        // if i is not the divisor of len(A), which means the A is not
        // able to be equally divided, we ignore them;
        if len(A)%i != 0 {
            continue
        }
        // we got the block size
        di := len(A) / i

        peakState := 0
        k := 0

        // this loop is for verifying whether each block has at least one
        // peak by checking the peak is inside A[k]~A[2k]-1
        // if current peak is not valid, we step down the next peak until
        // valid, then we move to the next block for finding valid peak;

        // once all the peaks are consumed, we can verify whether all the
        // blocks are valid with peak inside by checking the k value, 
        // if k reaches the 
        // final state, we can make sure that this solution is acceptable
        for {
            if peakState > len(peaks)-1 {
                break
            }
            if k >= i {
                break
            }
            if peaks[peakState] >= di*k && peaks[peakState] <= di*(k+1)-1 {
                peakState++
            } else {
                k++
            }
        }
        // if all peaks are checked truly inside the block, we can make
        // sure this divide solution is acceptable and record it in the
        // global max block size
        if k == i-1 && peakState == len(peaks) {
            maxBlocks = i
        }

    }
    return maxBlocks
}

解决方案

感谢您向代码添加更多注释。这个想法似乎有道理。如果法官报告了错误的答案，我会尝试使用随机数据和一些边缘情况以及强力控制，看看是否可以捕获大小合理的失败示例，并分析问题所在。

到目前为止，我自己想到的一种可能的方法是记录一个前缀数组，以便在 o(1) 中判断一个块是否有峰值。如果元素是峰则加 1，否则加 0。对于输入，

1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2

我们会有：

1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2
0  0  0  1  1  2  2  2  2  2  3  3

现在，当我们除法时，如果一个块的相对和为正，我们就知道它是否包含峰值：

1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2
0|0  0  0  1| 1  2  2  2| 2  2  3  3
a          b           c           d

如果第一个块不包含峰值，我们预计 b - a 等于 0，但我们得到 1，这意味着存在峰值。此方法将保证每个除数测试为 o(numblocks)。

我要尝试的第二件事是从最小除数（最大块大小）迭代到最大除数（最小块大小），但跳过可以被验证失败的较小除数除的除数。例如，如果 2 成功但 3 失败，则 6 不可能成功，但 4 仍然可以。

1 2 3 4 5 6 7 8 9 10 11 12
2          |
3      |       |
6  |   |   |   |    |
4 x  |x    |    x|    x

今天带大家了解了的相关知识，希望对你有所帮助；关于Golang的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~