※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 真假
: 今天只有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;
: }
: };
思路:
就記錄最大跟最小的
然後要避免最大跟最小的都來自同個array
所以跟之前的最大最小值就跟現在array的最大最小值相減
然後更新最大最小值
Python Code:
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
cur_max = arrays[0][-1]
cur_min = arrays[0][0]
result = 0
for i in range(1,len(arrays)):
result = max(result, cur_max-arrays[i][0], arrays[i][-1]-cur_min)
cur_max = max(cur_max, arrays[i][-1])
cur_min = min(cur_min, arrays[i][0])
return result