[leetcode/lintcode 题解] 算法面试真题详解:数组中最大的差值

简介: [leetcode/lintcode 题解] 算法面试真题详解:数组中最大的差值

描述
给 m 个数组, 每一个数组均为升序. 现在你可以从两个不同的数组中挑选两个整数(每一个数组选一个)并且计算差值. 我们将两个整数 a 和 b 之间的差定义为它们的绝对差 |a - b|. 你的任务是去找到最大的差值.

每一个给出的数组长度至少为 1. 至少有两个不为空的数组
m 个数组中所有整数的个数和在 [2, 10000]范围内.
m 个数组中所有的整数均将在[-10000, 10000]范围内.

在线评测地址:领扣题库官网

样例1
输入:[[1,2,3], [4,5], [1,2,3]]
输出:4
解释:
获得最大差值的一种方式是在第一个数组或第三个数组中取 1, 在第二个数组中取 5. 
样例2
输入:[[1,2,3,4,5,6,7,8,9],[0,10]]
输出:9

解题思路
我们在遍历m个数组时,对于第i个数组,记录前i-1个数组中的最大值和最小值,此时有res=max(res,abs(ai−maximum),abs(ai−minimum))
源代码

public class Solution {

    /**
     * @param arrs: an array of arrays
     * @return: return the max distance among arrays
     */
    public int maxDiff(int[][] arrs) {
        int res = 0, start = arrs[0][0], end = arrs[0][arrs[0].length - 1];
        for (int i = 1; i < arrs.length; i++) {
            res = Math.max(res, Math.max(Math.abs(arrs[i][0] - end), Math.abs(arrs[i][arrs[i].length - 1] - start)));
            start = Math.min(start, arrs[i][0]);
            end = Math.max(end, arrs[i][arrs[i].length - 1]);
        }
        return res;
    }
}

更多题解参考:九章官网solution

相关文章
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
316 0
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
1235 23
|
存储 监控 算法
关于员工上网监控系统中 PHP 关联数组算法的学术解析
在当代企业管理中,员工上网监控系统是维护信息安全和提升工作效率的关键工具。PHP 中的关联数组凭借其灵活的键值对存储方式,在记录员工网络活动、管理访问规则及分析上网行为等方面发挥重要作用。通过关联数组,系统能高效记录每位员工的上网历史,设定网站访问权限,并统计不同类型的网站访问频率,帮助企业洞察员工上网模式,发现潜在问题并采取相应管理措施,从而保障信息安全和提高工作效率。
333 7
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
487 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
337 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
开发者 索引 Python
这些年背过的面试题——LeetCode
本文是技术人面试系列LeetCode篇,一文带你详细了解,欢迎收藏!
|
C语言
【Amazon 面试题1】一个数组,里面得数出现的次数是偶数次,只有一个数出现的次数是奇数次,找出那个出现奇数次的数
本文介绍了解决Amazon面试题的一种方法,即在一个所有数字出现次数都是偶数,除了一个数字出现奇数次的数组中,利用异或运算的性质找出出现奇数次的数字,并提供了C语言实现的代码示例。
401 1
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
740 0
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
285 0

热门文章

最新文章