小红的数组权值

[题目链接](https://www.nowcoder.com/practice/383eb5dc6e8044f9b879f1848a6784e8)

思路

问题分析

给定数组 $\text{nums}$ ，需要把数字 $1, 2, \ldots, m$ 全部插入数组的任意位置，使得插入后相邻元素差的绝对值之和（即数组权值）最小。原数组的相对顺序保持不变。

关键观察：在某个间隙中插入数不会减少贡献

设原数组中有一对相邻元素 $a, b$ ，它们对权值的贡献是 $|a - b|$ 。如果在它们之间插入一个值 $x$ ，贡献变成 $|a - x| + |x - b|$ 。由三角不等式， $|a - x| + |x - b| \geq |a - b|$ ，当且仅当 $x$ 在 $a$ 和 $b$ 之间（含端点）时取等。

因此，如果插入的值在该间隙覆盖的范围 $[\min(a,b),\, \max(a,b)]$ 内，贡献不变；否则贡献增大。

哪些值可以"免费"插入？

考虑所有相邻间隙覆盖的值域范围的并集。由于数组中的值构成一条"路径"，从某个值走到另一个值，所有介于 $\min(\text{nums})$ 与 $\max(\text{nums})$ 之间的整数都能在某个间隙中找到覆盖——对它们来说，插入代价为零。

因此，只有超出原数组值域范围的数才会产生额外代价：

若 $\min(\text{nums}) > 1$ ，则 $1, 2, \ldots, \min(\text{nums}) - 1$ 需要额外处理。
若 $m > \max(\text{nums})$ ，则 $\max(\text{nums}) + 1, \ldots, m$ 需要额外处理。

最优插入越界值

以高于上界的值 $L = \max+1, \ldots, R = m$ 为例（低于下界的情况完全对称）。这些值是连续的一段，我们需要把它们一起插入到数组的某个位置（某个间隙、数组头部或尾部）。

插入到相邻元素 $(a, b)$ 之间时，最优是走"一头一尾"的路线，有两种走法：

$ $\text{cost}_1 = |a - L| + (R - L) + |R - b|$ $

$ $\text{cost}_2 = |a - R| + (R - L) + |L - b|$ $

额外代价为 $\min(\text{cost}_1, \text{cost}_2) - |a - b|$ 。

插入在数组头部或尾部时，额外代价为：

$ $(R - L) + \min(|e - L|,\; |e - R|)$ $

其中 $e$ 是头部/尾部元素。

遍历所有 $n - 1$ 个间隙加头尾两个位置，取最小额外代价即可。

最终答案

$ $\text{答案} = \text{原始权值} + \text{低值额外代价} + \text{高值额外代价}$ $

复杂度

时间复杂度： $O(n)$ ，一次遍历计算原始权值，再各一次遍历处理低值和高值。
空间复杂度： $O(1)$ ，只用常数额外空间。

代码

C++
Java
Python3
JavaScript

class Solution {
public:
    long long min_value(vector<int>& nums, int m) {
        int n = nums.size();
        long long weight = 0;
        int mn = nums[0], mx = nums[0];
        for (int i = 0; i < n; i++) {
            mn = min(mn, nums[i]);
            mx = max(mx, nums[i]);
            if (i > 0) weight += abs(nums[i] - nums[i - 1]);
        }

        // 处理低于下界的值 1..mn-1
        long long lowExtra = 0;
        if (mn > 1) {
            int L = 1, R = mn - 1, span = R - L;
            long long best = (long long)span + min(abs(nums[0] - L), abs(nums[0] - R));
            best = min(best, (long long)span + min(abs(nums[n - 1] - L), abs(nums[n - 1] - R)));
            for (int i = 0; i < n - 1; i++) {
                long long orig = abs(nums[i] - nums[i + 1]);
                long long c1 = (long long)abs(nums[i] - L) + span + abs(R - nums[i + 1]);
                long long c2 = (long long)abs(nums[i] - R) + span + abs(L - nums[i + 1]);
                best = min(best, min(c1, c2) - orig);
            }
            lowExtra = best;
        }

        // 处理高于上界的值 mx+1..m
        long long highExtra = 0;
        if (m > mx) {
            int L = mx + 1, R = m, span = R - L;
            long long best = (long long)span + min(abs(nums[0] - L), abs(nums[0] - R));
            best = min(best, (long long)span + min(abs(nums[n - 1] - L), abs(nums[n - 1] - R)));
            for (int i = 0; i < n - 1; i++) {
                long long orig = abs(nums[i] - nums[i + 1]);
                long long c1 = (long long)abs(nums[i] - L) + span + abs(R - nums[i + 1]);
                long long c2 = (long long)abs(nums[i] - R) + span + abs(L - nums[i + 1]);
                best = min(best, min(c1, c2) - orig);
            }
            highExtra = best;
        }

        return weight + lowExtra + highExtra;
    }
};

import java.util.*;

public class Solution {
    public long min_value(int[] nums, int m) {
        int n = nums.length;
        long weight = 0;
        int mn = nums[0], mx = nums[0];
        for (int i = 0; i < n; i++) {
            mn = Math.min(mn, nums[i]);
            mx = Math.max(mx, nums[i]);
            if (i > 0) weight += Math.abs(nums[i] - nums[i - 1]);
        }

        long lowExtra = 0;
        if (mn > 1) {
            int L = 1, R = mn - 1, span = R - L;
            long best = (long) span + Math.min(Math.abs(nums[0] - L), Math.abs(nums[0] - R));
            best = Math.min(best, (long) span + Math.min(Math.abs(nums[n - 1] - L), Math.abs(nums[n - 1] - R)));
            for (int i = 0; i < n - 1; i++) {
                long orig = Math.abs(nums[i] - nums[i + 1]);
                long c1 = (long) Math.abs(nums[i] - L) + span + Math.abs(R - nums[i + 1]);
                long c2 = (long) Math.abs(nums[i] - R) + span + Math.abs(L - nums[i + 1]);
                best = Math.min(best, Math.min(c1, c2) - orig);
            }
            lowExtra = best;
        }

        long highExtra = 0;
        if (m > mx) {
            int L = mx + 1, R = m, span = R - L;
            long best = (long) span + Math.min(Math.abs(nums[0] - L), Math.abs(nums[0] - R));
            best = Math.min(best, (long) span + Math.min(Math.abs(nums[n - 1] - L), Math.abs(nums[n - 1] - R)));
            for (int i = 0; i < n - 1; i++) {
                long orig = Math.abs(nums[i] - nums[i + 1]);
                long c1 = (long) Math.abs(nums[i] - L) + span + Math.abs(R - nums[i + 1]);
                long c2 = (long) Math.abs(nums[i] - R) + span + Math.abs(L - nums[i + 1]);
                best = Math.min(best, Math.min(c1, c2) - orig);
            }
            highExtra = best;
        }

        return weight + lowExtra + highExtra;
    }
}

class Solution:
    def min_value(self, nums: list, m: int) -> int:
        n = len(nums)
        weight = sum(abs(nums[i + 1] - nums[i]) for i in range(n - 1))
        mn, mx = min(nums), max(nums)

        low_extra = 0
        if mn > 1:
            L, R = 1, mn - 1
            span = R - L
            best = span + min(abs(nums[0] - L), abs(nums[0] - R))
            best = min(best, span + min(abs(nums[-1] - L), abs(nums[-1] - R)))
            for i in range(n - 1):
                orig = abs(nums[i] - nums[i + 1])
                c1 = abs(nums[i] - L) + span + abs(R - nums[i + 1])
                c2 = abs(nums[i] - R) + span + abs(L - nums[i + 1])
                best = min(best, min(c1, c2) - orig)
            low_extra = best

        high_extra = 0
        if m > mx:
            L, R = mx + 1, m
            span = R - L
            best = span + min(abs(nums[0] - L), abs(nums[0] - R))
            best = min(best, span + min(abs(nums[-1] - L), abs(nums[-1] - R)))
            for i in range(n - 1):
                orig = abs(nums[i] - nums[i + 1])
                c1 = abs(nums[i] - L) + span + abs(R - nums[i + 1])
                c2 = abs(nums[i] - R) + span + abs(L - nums[i + 1])
                best = min(best, min(c1, c2) - orig)
            high_extra = best

        return weight + low_extra + high_extra

function min_value(nums, m) {
    const n = nums.length;
    let weight = 0;
    let mn = nums[0], mx = nums[0];
    for (let i = 0; i < n; i++) {
        mn = Math.min(mn, nums[i]);
        mx = Math.max(mx, nums[i]);
        if (i > 0) weight += Math.abs(nums[i] - nums[i - 1]);
    }

    let lowExtra = 0;
    if (mn > 1) {
        const L = 1, R = mn - 1, span = R - L;
        let best = span + Math.min(Math.abs(nums[0] - L), Math.abs(nums[0] - R));
        best = Math.min(best, span + Math.min(Math.abs(nums[n - 1] - L), Math.abs(nums[n - 1] - R)));
        for (let i = 0; i < n - 1; i++) {
            const orig = Math.abs(nums[i] - nums[i + 1]);
            const c1 = Math.abs(nums[i] - L) + span + Math.abs(R - nums[i + 1]);
            const c2 = Math.abs(nums[i] - R) + span + Math.abs(L - nums[i + 1]);
            best = Math.min(best, Math.min(c1, c2) - orig);
        }
        lowExtra = best;
    }

    let highExtra = 0;
    if (m > mx) {
        const L = mx + 1, R = m, span = R - L;
        let best = span + Math.min(Math.abs(nums[0] - L), Math.abs(nums[0] - R));
        best = Math.min(best, span + Math.min(Math.abs(nums[n - 1] - L), Math.abs(nums[n - 1] - R)));
        for (let i = 0; i < n - 1; i++) {
            const orig = Math.abs(nums[i] - nums[i + 1]);
            const c1 = Math.abs(nums[i] - L) + span + Math.abs(R - nums[i + 1]);
            const c2 = Math.abs(nums[i] - R) + span + Math.abs(L - nums[i + 1]);
            best = Math.min(best, Math.min(c1, c2) - orig);
        }
        highExtra = best;
    }

    return weight + lowExtra + highExtra;
}
module.exports = { min_value };