20250219力扣每日一题

知识点

abs()函数：用来计算一个数的绝对值

解题思路

由于给定的数组都是有序的，所以每个数组i的第一个元素i[0]都是该数组最小的元素，最后一个元素i[i.size() - 1]都是该数组最大的元素
给定计算的最大距离的两个端点应该来自不同的数组，给定数组a和b，那么最大距离应该在a[a.size() - 1] - b[0]和b[b.size() - 1] - a[0]中出现。但是，遍历所有数组的时间复杂度容易造成超时
考虑单次扫描数组，并跟踪更新目前为止找到的最小值点min_val和最大值点max_val，这些极值点可以被视为目前所有已经遍历过的数组的极值点
对于一个新遍历到的数组a，我们可以将a[n - 1] - min_value与max_value - a[0]中的最大值与res进行比较，更新最大距离，并更新min_value和max_value
遍历结束后，返回res

实现代码

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int res = 0;
        int n = arrays[0].size();
        int min_val = arrays[0][0];
        int max_val = arrays[0][n - 1];
        for(int i = 1; i < arrays.size(); i ++){
            n = arrays[i].size();
            res = max(res, max(abs(arrays[i][n - 1] - min_val),
                               abs(max_val - arrays[i][0])));
            min_val = min(min_val, arrays[i][0]);
            max_val = max(max_val, arrays[i][n - 1]);
        }
        return res;
    }
};

知识点

解题思路

实现代码

Enjoy Reading This Article?