2026-08-10使数组非递减需要的最小累计值。用go语言有一个长度为 n 的整数数组。你可以多次执行下面的操作选择任意一个连续非空子数组以及任意一个正整数 x。将该子数组里的每个数都加上 x。你的目标是通过一系列这样的操作让整个数组变得“非递减”也就是从左到右每个数都 ≤ 后一个数。每次操作都会消耗一个 x就是你这次加上的那个正整数所有操作消耗的 x 加起来就是总代价。请你计算并返回在所有能让数组变成非递减的操作方案中这个总代价的最小可能值。1 n nums.length 100000。1 nums[i] 1000000000。输入 nums [3,3,2,1]。输出 2。解释一种最优操作方案为选择子数组 [2…3]并增加 x 1得到 [3, 3, 3, 2]选择子数组 [3…3]并增加 x 1得到 [3, 3, 3, 3]数组变为非递减所选 x 的总和为 1 1 2。题目来自力扣3914。详细执行步骤初始化总代价用一个变量例如ans记录累计的 x 总和初始值为 0。遍历数组寻找下降点从第二个元素开始索引i 1向右扫描到最后一个元素依次检查相邻元素nums[i-1]和nums[i]的关系。计算当前相邻差对于每一对相邻元素计算diff nums[i-1] - nums[i]。如果diff 0说明出现下降前一个数大于后一个数必须通过操作将nums[i]及其后面的部分至少增加diff才能让nums[i]不小于nums[i-1]。这是不可回避的最小代价。如果diff 0说明已经满足非递减不需要任何操作代价为 0。累加必须的代价若diff 0则将diff累加到总代价ans中否则加 0相当于跳过。逻辑上“修改”数组无需实际修改虽然代码中没有真的修改数组但可以想象当我们决定付出diff的代价后相当于把从i开始到数组末尾的所有元素都增加了diff。这样一来对于后续的所有相邻对由于它们都被加上了相同的值它们之间的差值保持不变。因此在后续扫描中我们仍然可以直接使用原数组的值计算差值结果不会受到影响。这也是为什么不需要在内存中维护更新后的数组。完成遍历当循环结束ans中存储的就是使整个数组变为非递减所需的最小 x 总和。示例推演以nums [3, 3, 2, 1]为例索引 13与3差值为 0不加。索引 23与2差值为 1累加ans 1。逻辑上将nums[2..3]都加 1数组变为[3, 3, 3, 2]。索引 3比较时使用的是原数组的nums[2]2和nums[3]1差值2-11累加ans 2。逻辑上再将nums[3..3]加 1数组最终变为[3, 3, 3, 3]。总代价为 2与题目示例一致。复杂度分析时间复杂度整个过程只对数组进行了一次从左到右的单次扫描每个元素只访问一次循环内执行常数时间的减法和取最大值操作。因此时间复杂度为O(n)其中 n 是数组长度。额外空间复杂度除了输入的数组外只使用了固定的几个变量总代价变量、循环计数器等不随数据规模增长。因此额外空间复杂度为O(1)。Go完整代码如下packagemainimport(fmt)funcminOperations(nums[]int)(ansint64){fori:1;ilen(nums);i{ansint64(max(nums[i-1]-nums[i],0))}return}funcmain(){nums:[]int{3,3,2,1}result:minOperations(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefminOperations(nums:List[int])-int: 返回使数组变为非递减所需的最小操作总和每次操作可以对子数组加上任意正整数 x 总代价为所有操作的 x 之和。 ans0foriinrange(1,len(nums)):# 当前一个数大于后一个数时必须至少增加后一个数及之后的部分# 以消除这个“下降”最小的增加量就是两者的差值。ansmax(nums[i-1]-nums[i],0)returnansif__name____main__:nums[3,3,2,1]resultminOperations(nums)print(result)C完整代码如下#includeiostream#includevector#includealgorithm// for std::maxlonglongminOperations(conststd::vectorintnums){longlongans0;for(size_t i1;inums.size();i){ansstd::max(nums[i-1]-nums[i],0);}returnans;}intmain(){std::vectorintnums{3,3,2,1};longlongresultminOperations(nums);std::coutresultstd::endl;// 输出 2return0;}