真假
今天只有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;
}
};