我正在尝试解决这个代码难题：

给定一个整数数组arr，通过一次操作，可以将数组中的任意元素减少 1。找出使该数组成为双调*数组n所需的最少操作数。

* 双调数组的前缀和后缀中可以有任意数量的零。非零部分应从 1 增加到某个整数k，然后减少到 1。

双调数组的示例：[0,1,2,3,2,1,0,0]。

示例 1

输入：[3,3,3,3,3]

答案：6（最终数组[1,2,3,2,1]：）

示例 2

输入：[1,1,3,1,1]

答案：3（最终数组[0,1,2,1,0]：）

示例 3：

输入：[1,2,1,3,2]

答案：5（最终数组：[1,2,1,0,0]或[0,0,1,2,1]）

我可以看到如下的强力解决方案：

  • 设置minimum为无穷大
  • 对于中的每个索引arr：

    • 对于 0 至 范围内的每个值arr[index]：

      • 创建一个以arr[index] = value峰值为单位的双调数组。
      • 如果这是可能的，并且它只能通过从以下方面进行减少来形成arr：

        • 计算所需减少的数量
        • 如果减少的次数小于minimum：

          • 更新minimum此结果
  • 返回minimum

但是，这种方法的时间复杂度很差，对于大输入，运行时间令人难以接受。有没有一种有效的算法可以解决这个问题？

5

  • 不是家庭作业问题。在亚马逊面试时遇到这个问题。无法解决。在任何地方都找不到类似的问题。所以任何帮助都会很感激。


    – 

  • 您是否搜索过如何？这有帮助吗？


    – 


  • @abra 允许的操作不一样。我怀疑该链接能否解决这个问题。


    – 

  • @systummm 如果我们不知道您遇到的问题，我们就无法帮助您。花点时间自己解决问题，根据您尝试过的方法和无效的方法编辑您的问题。目前这个问题不合适（实际上没有问题），但很接近了。


    – 

  • 3
    @AloisChristen “如果我们不知道你被困在哪里，我们就无法帮助你”——这实际上很少与算法问题相关。看到一个完全偏离目标的尝试对任何人都没有多大帮助。


    – 


最佳答案
1

这可以用线性时间复杂度完成：

获取数组中所有值的总和。

对数组进行前向扫描，进行必要的缩减，以确保某个值永远不会比其（可能已经更新的）前任值大 1。第一个元素的前任值应为 0。

在更新后的数组上，以相反的方向重复相同的操作。

经过这两个步骤，我们执行了所需的最小缩减，以获得一个数组，该数组的元素永远不会大于任何一个邻居加 1，当没有邻居时，再次取 0 作为邻居值。

找到此数组中的最大值，该值将成为双调数组的峰值。如果有多个位置可供选择，这无关紧要，因为双调数组的最终总和将相同：实现该值的操作次数是原始数组的总和与最终数组的总和之间的差值。

最终数组总和是峰值的平方——实际上没有必要将数组设为双调。例如，如果峰值为 3，则双调数组中的值的总和将为 1+2+3+2+1 = 9。

下面是可运行的 JavaScript 代码片段的实现，运行您给出的三个示例：

function makeBitonic(arr) {
    // Get sum of input array's values
    let sum = 0;
    for (let i = 0; i < arr.length; i++) sum += arr[i];
    // Sweep forward and backward, clipping the array so two neighboring values 
    //   never differ by more than 1, and the outer values are never more than 1.
    for (let sweep = 0; sweep < 2; sweep++) {
        let max = 0; // Maximum value allowed in array element
        for (let i = 0; i < arr.length; i++) {
            max++; // Allow one more than previous limit
            if (arr[i] > max) {
                arr[i] = max;  // clip
            } else {
                max = arr[i];
            }
        }
        arr.reverse(); // Prepare for the reverse sweep
    }
    let m = Math.max(...arr);
    return sum - m * m; // m² is final sum
}

const tests = [
    [[3,3,3,3,3], 6],
    [[1,1,3,1,1], 3],
    [[1,2,1,3,2], 5],
    [[9,9,0,9,9], 35],
];

for (const [arr, expected] of tests) {
    console.log("Test: ", JSON.stringify(arr), "expect", expected);
    const got = makeBitonic(arr);
    if (got != expected) throw "Wrong result, got " + got;
}

1

  • 1
    非常简洁明了的答案。+1


    –