class Solution {
public:
int minNumberOperations(vector<int>& target) {
}
};
1526. 形成目标数组的子数组最少增加次数
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。
请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：
initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。答案保证在 32 位有符号整数以内。
示例 1：
输入：target = [1,2,3,2,1] 输出：3 解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。 [0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。 [1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。 [1,2,2,2,1] 将下表为 2 的元素增加 1 。 [1,2,3,2,1] 得到了目标数组。
示例 2：
输入：target = [3,1,1,2] 输出：4 解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。
示例 3：
输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。
示例 4：
输入：target = [1,1,1,1] 输出：1
提示：
1 <= target.length <= 10^51 <= target[i] <= 10^5原站题解
rust 解法, 执行用时: 12 ms, 内存消耗: 3.2 MB, 提交时间: 2023-09-21 10:01:37
impl Solution {
pub fn min_number_operations(target: Vec<i32>) -> i32 {
use std::cmp;
let mut ans = target[0];
for i in 1..target.len() {
ans += cmp::max(target[i] - target[i-1], 0)
}
ans
}
}
golang 解法, 执行用时: 108 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-21 09:59:42
// 差分数组
func minNumberOperations(target []int) int {
ans, n := target[0], len(target)
for i := 1; i < n; i++ {
ans += max(target[i] - target[i-1], 0)
}
return ans
}
func max(a, b int) int { if a > b { return a }; return b }
python3 解法, 执行用时: 156 ms, 内存消耗: 24.6 MB, 提交时间: 2023-09-21 09:58:44
class Solution:
def minNumberOperations(self, target: List[int]) -> int:
ans, n = target[0], len(target)
for i in range(1, n):
ans += max(target[i] - target[i-1], 0)
return ans
java 解法, 执行用时: 2 ms, 内存消耗: 52.9 MB, 提交时间: 2023-09-21 09:57:36
class Solution {
public int minNumberOperations(int[] target) {
int n = target.length;
int ans = target[0];
for (int i = 1; i < n; ++i) {
ans += Math.max(target[i] - target[i - 1], 0);
}
return ans;
}
}
cpp 解法, 执行用时: 92 ms, 内存消耗: 71.7 MB, 提交时间: 2023-09-21 09:56:52
// 考虑每个元素左侧相邻元素的贡献值
class Solution {
public:
int minNumberOperations(vector<int>& target) {
int n = target.size();
int ans = target[0];
for (int i = 1; i < n; ++i) {
ans += max(target[i] - target[i - 1], 0);
}
return ans;
}
};