Maximum Distance in Arrays[M,Array,Greedy]

You are given m arrays, where each array is sorted in ascending order.

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|.

Return the maximum distance.

 

Example 1:

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4
Explanation: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Example 2:

Input: arrays = [[1],[1]]
Output: 0

 

Constraints:

• m == arrays.length
• 2 <= m <= 105
• 1 <= arrays[i].length <= 500
• -104 <= arrays[i][j] <= 104
• arrays[i] is sorted in ascending order.
• There will be at most 105 integers in all the arrays.

1. C++

한 array에서 min / max를 모두 pick해도 되는 경우엔 아래가 맞다.

근데 코드를 다 짜고 보니까 한 array에서 그렇게 고르지 말라고 합디다..

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int min_num = INT_MAX;
        int max_num = INT_MIN;

        for(int i=0;i<arrays.size();i++){
            int size = arrays[i].size();
            if(arrays[i][0]<min_num){
                min_num = arrays[i][0];
            }
            if(arrays[i][size-1]>max_num){
                max_num = arrays[i][size-1];
            }
        }
        return max_num - min_num;
    }
};

 

한 array pick 조건까지 반영을 해보면..

 

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int min_num = arrays[0].front();
        int max_num = arrays[0].back();
        int dist = 0;

        for(int i=1;i<arrays.size();i++){
            dist = max(dist,arrays[i].back()-min_num);
            dist = max(dist,max_num - arrays[i].front());

            min_num = min(min_num,arrays[i].front());
            max_num = max(max_num,arrays[i].back());
        }
        return dist;
    }
};

 

2. Python

똑같은 메커니즘

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        minnum = arrays[0][0]
        maxnum = arrays[0][-1]
        dist = 0
        for i in range(1,len(arrays)):
            dist = max(dist,arrays[i][-1]-minnum)
            dist = max(dist,maxnum-arrays[i][0])

            minnum = min(minnum,arrays[i][0])
            maxnum = max(maxnum,arrays[i][-1])
        return dist

 

3. C

역시 array를 다루다보니 좀 너저지분하다.

int maxDistance(int** arrays, int arraysSize, int* arraysColSize) {
    int min_num = arrays[0][0];
    int max_num = arrays[0][arraysColSize[0] - 1];
    int max_distance = 0;

    for (int i = 1; i < arraysSize; i++) {
        int first_element = arrays[i][0];
        int last_element = arrays[i][arraysColSize[i] - 1];

        // 현재 배열의 첫 번째 및 마지막 요소와 글로벌 최소/최대 비교하여 거리 계산
        int distance1 = abs(last_element - min_num);
        int distance2 = abs(max_num - first_element);
        if (distance1 > max_distance) max_distance = distance1;
        if (distance2 > max_distance) max_distance = distance2;

        // 글로벌 최소 및 최대값 업데이트
        if (first_element < min_num) min_num = first_element;
        if (last_element > max_num) max_num = last_element;
    }

    return max_distance;
}

메커니즘은 같다.