LeetCode 1131. 绝对值表达式的最大值

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 数学

题目描述

✅ 1131. 绝对值表达式的最大值

image-20260929110110147

题意分析

在所有下标对 i、j 中，最大化两组数组值的绝对差与下标绝对差之和。三个差必须来自同一对下标，不能把三项各自的最大值独立相加。

解法：四种符号 + 极值扫描

核心思路

[!blue]

一个绝对值满足 |x| = max(x, -x)。因此对固定的 i、j，给三个差分别选择正号或负号，八种线性表达式中的最大值，就等于原来的三个绝对值之和。再对所有下标对求最大，可以交换这两层有限枚举的顺序，先固定符号，再找最好的下标对。

固定三个符号 s、t、u 后，令 F(i) = s*arr1[i] + t*arr2[i] + u*i，对应表达式就是 F(i) - F(j)。i 与 j 可以自由选择，所以这一差值的最大值恰好是 max F - min F，用一次扫描记录最大值与最小值即可，不再需要枚举两两下标。

八种符号还可减半。如果同时把三个符号取反，整个 F 也取反，但极差保持不变：max(-F) - min(-F) = max(F) - min(F)。所以每种下标系数为负一的情况，都与一组下标系数为正一的情况等价。固定 u = 1，只枚举两个数组系数 s、t 的四种组合就足够。

对每组符号，扫描 s*arr1[i] + t*arr2[i] + i 的两端极值，用它们的差更新全局答案。极值从下标零的实际表达式初始化，避免把输入中不存在的零误当作候选。四组符号分别处理后，其中最大极差就是原问题的最大值。

解题步骤

  1. 用两位掩码枚举两个数组的正负号，共四组，下标项始终取正号。
  2. 计算下标零的线性式，作为当前最小值和最大值。
  3. 扫描剩余下标，计算同一个线性式并更新两端极值。
  4. 用当前最大值减最小值更新全局答案，完成四组后返回。

代码实现

class Solution {
    public int maxAbsValExpr(int[] arr1, int[] arr2) {
        int answer = 0;

        for (int mask = 0; mask < 4; mask++) {
            int sign1 = (mask & 1) == 0 ? 1 : -1;
            int sign2 = (mask & 2) == 0 ? 1 : -1;
            int first = sign1 * arr1[0] + sign2 * arr2[0];
            int low = first;
            int high = first;

            // 四种符号各扫描一次，记录同一线性式的两端极值。
            for (int i = 1; i < arr1.length; i++) {
                int value = sign1 * arr1[i] + sign2 * arr2[i] + i;

                low = Math.min(low, value);
                high = Math.max(high, value);
            }

            answer = Math.max(answer, high - low);
        }

        return answer;
    }
}

func maxAbsValExpr(arr1 []int, arr2 []int) int {
    answer := 0
    for mask := 0; mask < 4; mask++ {
        sign1, sign2 := 1, 1
        if mask&1 != 0 {
            sign1 = -1
        }
        if mask&2 != 0 {
            sign2 = -1
        }
        first := sign1*arr1[0] + sign2*arr2[0]
        low, high := first, first

        // 四种符号各扫描一次，记录同一线性式的两端极值。
        for i := 1; i < len(arr1); i++ {
            value := sign1*arr1[i] + sign2*arr2[i] + i
            if value < low {
                low = value
            }
            if value > high {
                high = value
            }
        }
        if high-low > answer {
            answer = high - low
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$，每种符号扫描一次，共固定四次扫描。
  • 空间复杂度：$O(1)$，只保存符号、线性式极值和答案。

关键点总结

[!green]

  • 先枚举绝对值的符号，把两下标表达式拆成 F(i) - F(j)。
  • 对同一个线性式取极差，自动选择最佳下标对。
  • 全部符号同时反转不改变极差，因此只保留四种情况。

易错点总结

[!yellow]

  • 分别最大化三个绝对值再相加，三项最优值可能对应不同下标对。
  • 省略下标项 i，会漏掉距离 |i-j| 的贡献。
  • 只检查两个数组都取正号，无法覆盖其他符号方向。
  • 取单个 F 的绝对值不能代替极差；初始化为零也可能引入不存在的候选值。

相似题目

题目 难度 关联与区别
624. 数组列表中的最大距离 中等 一维绝对差可由最小最大值求出，本题对多个绝对值枚举符号后也转成线性式的最大最小差。
3102. 最小化曼哈顿距离 困难 同样通过符号变换处理曼哈顿距离，本题还把下标差作为第三个坐标维度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/21715224
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！