2026-08-10：使数组非递减需要的最小累计值。用go语言，有一个长度为 n 的整数数组。你可以多次执行下面的操作： – 选择任意一个连续非空

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。

详细执行步骤

1.初始化总代价
用一个变量（例如ans）记录累计的 x 总和，初始值为 0。

2.遍历数组，寻找下降点
从第二个元素开始（索引i = 1）向右扫描到最后一个元素，依次检查相邻元素nums[i-1]和nums[i]的关系。

3.计算当前相邻差
对于每一对相邻元素，计算diff = nums[i-1] - nums[i]。

• 如果diff > 0，说明出现下降（前一个数大于后一个数），必须通过操作将nums[i]及其后面的部分至少增加diff才能让nums[i]不小于nums[i-1]。这是不可回避的最小代价。

• 如果diff <= 0，说明已经满足非递减，不需要任何操作，代价为 0。

4.累加必须的代价
若diff > 0，则将diff累加到总代价ans中；否则加 0（相当于跳过）。

5.逻辑上“修改”数组（无需实际修改）
虽然代码中没有真的修改数组，但可以想象：当我们决定付出diff的代价后，相当于把从i开始到数组末尾的所有元素都增加了diff。这样一来，对于后续的所有相邻对，由于它们都被加上了相同的值，它们之间的差值保持不变。因此在后续扫描中，我们仍然可以直接使用原数组的值计算差值，结果不会受到影响。这也是为什么不需要在内存中维护更新后的数组。

6.完成遍历
当循环结束，ans中存储的就是使整个数组变为非递减所需的最小 x 总和。

示例推演

以nums = [3, 3, 2, 1]为例：

• 索引 1：3与3，差值为 0，不加。

• 索引 2：3与2，差值为 1，累加ans = 1。逻辑上将nums[2..3]都加 1，数组变为[3, 3, 3, 2]。

• 索引 3：比较时使用的是原数组的nums[2]=2和nums[3]=1，差值2-1=1，累加ans = 2。逻辑上再将nums[3..3]加 1，数组最终变为[3, 3, 3, 3]。

• 总代价为 2，与题目示例一致。

复杂度分析

•时间复杂度：整个过程只对数组进行了一次从左到右的单次扫描，每个元素只访问一次，循环内执行常数时间的减法和取最大值操作。因此时间复杂度为O(n)，其中 n 是数组长度。

•额外空间复杂度：除了输入的数组外，只使用了固定的几个变量（总代价变量、循环计数器等），不随数据规模增长。因此额外空间复杂度为O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func minOperations(nums []int) (ans int64) {
    for i := 1; i < len(nums); i++ {
        ans += int64(max(nums[i-1]-nums[i], 0))
    }
    return
}

 func main() {
    nums := []int{3, 3, 2, 1}
    result := minOperations(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def minOperations(nums: List[int]) -> int:
    """
    返回使数组变为非递减所需的最小操作总和（每次操作可以对子数组加上任意正整数 x，
    总代价为所有操作的 x 之和）。
    """
    ans = 0
    for i in range(1, len(nums)):
        # 当前一个数大于后一个数时，必须至少增加后一个数（及之后的部分）
        # 以消除这个“下降”，最小的增加量就是两者的差值。
        ans += max(nums[i-1] - nums[i], 0)
    return ans

 if __name__ == "__main__":
    nums = [3, 3, 2, 1]
    result = minOperations(nums)
    print(result)

C++完整代码如下：

  

  

  

   
// for std::max

 long long minOperations(const std::vector& nums) {
    long long ans = 0;
    for (size_t i = 1; i < nums.size(); ++i) {
        ans += std::max(nums[i-1] - nums[i], 0);
    }
    return ans;
}

 int main() {
    std::vector nums = {3, 3, 2, 1};
    long long result = minOperations(nums);
    std::cout << result << std::endl; // 输出 2
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。