[leetcode]: 624. Maximum Distance in Arrays

野性酷女 2022-06-14 10:56 108阅读 0赞

# 1.题目 #

Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.  
给m个已经排序好的数组，从两个数组中分别挑选一个数字，使得差最大，求最大的差  
Example 1:  
Input:  
\[\[1,2,3\],  
\[4,5\],  
\[1,2,3\]\]  
Output: 4  
Explanation:  
从\[1,2,3\]中取1，\[4,5\]中取5。最大差为5-1=4

# 2.分析 #

最小值来源于每个数组中下标为0的元素  
最大值来源于每个数组中下标为len-1的元素  
注意：不能单纯找最大最小值，因为可能来自同一数组。

# 3.代码 #

int maxDistance(vector<vector<int>>& arrays) {
        int maxV = arrays[0][arrays[0].size() - 1];
        int minV = arrays[0][0];
        int diff = INT_MIN;
        for (int i = 1; i < arrays.size(); i++) {
            diff = diff < maxV - arrays[i][0] ? maxV - arrays[i][0] : diff;
            diff = diff < arrays[i][arrays[i].size() - 1] - minV ? arrays[i][arrays[i].size() - 1] - minV : diff;
            maxV = maxV < arrays[i][arrays[i].size() - 1] ? arrays[i][arrays[i].size() - 1] : maxV;
            minV = minV > arrays[i][0] ? arrays[i][0] : minV;
        }
        return diff;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，108人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Binary Search)1385. Find the Distance Value Between Two Arrays

1.问题 Given two integer arrays arr1 and arr2, and the integer d, return the distance v

水深无声/ 2023年09月25日 23:08/ 0 赞/ 57 阅读

相关 LeetCode（Array)1389. Create Target Array in the Given Order

1.问题 Given two arrays of integers nums and index. Your task is to create target array

╰半橙微兮°/ 2023年09月23日 22:40/ 0 赞/ 121 阅读

相关 LeetCode - Medium - 863. All Nodes Distance K in Binary Tree

Topic Tree Depth-first Search Breadth-first Search Description [https://

傷城~/ 2022年10月05日 02:57/ 0 赞/ 75 阅读

相关 Leetcode 1030. Matrix Cells in Distance Order

文章作者：Tyan 博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1] 1. Description ![Matrix C

以你之姓@/ 2022年09月09日 00:11/ 0 赞/ 12 阅读

相关 Search in Rotated Sorted Array--LeetCode

题目： Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.

红太狼/ 2022年08月05日 13:14/ 0 赞/ 21 阅读

相关 LeetCode - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert wo

左手的ㄟ右手/ 2022年08月04日 12:45/ 0 赞/ 72 阅读

相关 leetcode Edit Distance

题目 Given two words word1 and word2, find the minimum number of steps required to conv

约定不等于承诺〃/ 2022年08月01日 11:18/ 0 赞/ 198 阅读

相关 [leetcode]: 624. Maximum Distance in Arrays

1.题目 Given m arrays, and each array is sorted in ascending order. Now you can pick up

野性酷女/ 2022年06月14日 10:56/ 0 赞/ 109 阅读

相关【leetcode】1043. Partition Array for Maximum Sum

题目如下： > Given an integer array `A`, you partition the array into (contiguous) subarrays

雨点打透心脏的1/2处/ 2022年01月10日 06:13/ 0 赞/ 181 阅读

相关 leetcode--Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert wo

短命女/ 2021年10月25日 12:40/ 0 赞/ 283 阅读