Re: [閒聊] 每日leetcode

看板Marginalman作者DJYOMIYAHINA (通通打死)時間1年前 (2024/08/16 08:44)推噓5(5推 0噓 3→)

留言8則, 6人參與討論串721/1548 (看更多)

真假今天只有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; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723769049.A.1F7.html ※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 08/16/2024 08:45:32

推

JerryChungYC

08/16 08:45, 1年前 , 1^F

08/16 08:45, 1^F

→

JerryChungYC

08/16 08:45, 1年前 , 2^F

08/16 08:45, 2^F