真假
今天只有premium进得来喔 我以为大家都可以==
我把题目贴上来
624. Maximum Distance in Arrays
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 <= 10^5
1 <= arrays[i].length <= 500
-10^4 <= arrays[i][j] <= 10^4
arrays[i] is sorted in ascending order.
There will be at most 10^5 integers in all the arrays.
思路
好像也不算dp 就traverse过去
我这边的dp[i]代表从第i个array取一个，然后从第[0,i-1]的arrays取一个
的距离最大值
其实只要maintain arrays[0:i-1][:]里面的minimum跟maximum
持续跟arrays[i]里面的第一个数字跟最后一个数字做答案更新就可
class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
int max_cur = INT_MIN;
int min_cur = INT_MAX;
int dp;
// m>=2, init dp
dp = max(abs(arrays[0][0]-arrays[1].back()),
abs(arrays[0].back()-arrays[1][0]));
max_cur = max(arrays[0].back(), arrays[1].back());
min_cur = min(arrays[0][0], arrays[1][0]);
int ans = dp;
for(int i=2; i<arrays.size(); i++) {
dp = max(abs(arrays[i][0]-max_cur),
abs(arrays[i].back()-min_cur));
ans = max(ans, dp);
max_cur = max(max_cur, arrays[i].back());
min_cur = min(min_cur, arrays[i][0]);
}
return ans;
}
};