我正在尝试解决这个代码难题:
给定一个整数数组
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
此结果
- 更新
- 创建一个以
- 对于 0 至 范围内的每个值
- 返回
minimum
但是,这种方法的时间复杂度很差,对于大输入,运行时间令人难以接受。有没有一种有效的算法可以解决这个问题?
5
最佳答案
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
–
|
–
–
–
–
–
|