Medium
Related Topics: Array / Greedy
LeetCode Source

解題想法

題目唯一要注意的點就是 arrays 最大最小不能取同一個

其他基本上就是比較當前 arrays 最小，也就是第一個有沒有比之前更小

另外，當前 arrays 最大，也就是最後一個有沒有比之前更大

透過 res 儲存最大減去最小的值

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Python

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        min_val = arrays[0][0]
        max_val = arrays[0][-1]
        res = 0
        
        for i in range(1, len(arrays)):
            res = max(res, abs(arrays[i][-1] - min_val), abs(max_val - arrays[i][0]))
            
            min_val = min(min_val, arrays[i][0])
            max_val = max(max_val, arrays[i][-1])
        
        return res

C++

class Solution {
public:
    int maxDistance(std::vector<std::vector<int>>& arrays) {
        int min_val = arrays[0][0];
        int max_val = arrays[0].back();
        int res = 0;

        for (int i = 1; i < arrays.size(); ++i) {
            res = std::max(result, std::abs(arrays[i].back() - min_val));
            res = std::max(result, std::abs(max_val - arrays[i][0]));

            min_val = std::min(min_val, arrays[i][0]);
            max_val = std::max(max_val, arrays[i].back());
        }

        return res;
    }
};