algorithm-difference-array
差分数组
1234a[0] a[1] a[2] a[3] a[4] (0)差分数组: a[0] a[1]-a[0] a[2]-a[1] a[3]-a[2] a[4]-a[3] (-a[4])对差分数组求前缀和: a[0] a[1] a[2] a[3] a[4] (0)// 考虑末尾0(-a[4]),那么差分数组之和sum=0
前缀和就是离散版本的“求积分”,差分数组就是离散版本的“求微分”
形成目标数组的子数组最少增加次数
给你一个整数数组 target 和一个数组 initial ,initial 数组与 target 数组有同样的维度,且一开始全部为 0 。
请你返回从 initial 得到 target 的最少操作次数,每次操作需遵循以下规则:
在 initial 中选择 任意 子数组,并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1:
1234567输入:target = [1,2,3,2,1]输出:3解释:我们需要至少 3 次操作从 intial 数组得到 target 数组。[0,0,0,0,0] 将下标为 0 到 4 的元素(包 ...