[Swift]LeetCode1131.绝对值表达式的最大值|MaximumofAbsoluteValueExpression ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/11223723.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given two arrays of integers with equal lengths, return the maximum value of:

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

where the maximum is taken over all 0 <= i, j < arr1.length.

Example 1:

Input: arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
Output: 13

Example 2:

Input: arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
Output: 20

Constraints:

2 <= arr1.length == arr2.length <= 40000
-10^6 <= arr1[i], arr2[i] <= 10^6

给你两个长度相等的整数数组，返回下面表达式的最大值：

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

其中下标 i，j 满足 0 <= i, j < arr1.length。

示例 1：

输入：arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
输出：13

示例 2：

输入：arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
输出：20

提示：

2 <= arr1.length == arr2.length <= 40000
-10^6 <= arr1[i], arr2[i] <= 10^6

192ms

 1 class Solution {
 2     func maxAbsValExpr(_ arr1: [Int], _ arr2: [Int]) -> Int {
 3         let n = arr1.count
 4         var closet = 0
 5         var cur = 0
 6         var res = 0
 7         for p in [-1,1] {
 8             for q in [-1, 1] {
 9                 closet = arr1[0] * p + arr2[0] * q
10                 for i in 1 ..< n {
11                     cur = arr1[i] * p + arr2[i] * q + i
12                     res = max(res, cur - closet)
13                     closet = min(closet, cur)
14                 }
15             }
16         }
17         return res
18     }
19 }

Runtime: 196 ms

Memory Usage: 21.3 MB

 1 class Solution {
 2     func maxAbsValExpr(_ arr1: [Int], _ arr2: [Int]) -> Int {
 3         var n:Int = arr1.count
 4         var ans:Int = 0
 5         var maxmm:Int = Int.min / 2
 6         var maxmp:Int = Int.min / 2
 7         var maxpm:Int = Int.min / 2
 8         var maxpp:Int = Int.min / 2
 9         for i in 0..<n
10         {
11             maxmm = max(maxmm, -arr1[i] - arr2[i]-i)
12             maxmp = max(maxmp, -arr1[i] + arr2[i]-i)
13             maxpm = max(maxpm, arr1[i] - arr2[i]-i)
14             maxpp = max(maxpp, arr1[i] + arr2[i]-i)
15             ans = max(ans, maxmm + arr1[i] + arr2[i]+i)
16             ans = max(ans, maxmp + arr1[i] - arr2[i]+i)
17             ans = max(ans, maxpm - arr1[i] + arr2[i]+i)
18             ans = max(ans, maxpp - arr1[i] - arr2[i]+i)
19         }
20         return ans        
21     }
22 }

204ms

 1 class Solution {
 2     func maxAbsValExpr(_ arr1: [Int], _ arr2: [Int]) -> Int {
 3         var ans = 0
 4         
 5         for i in [-1,1] {
 6             for j in [-1,1]{
 7                 var best = arr1[0] * i + arr2[0] * j
 8                 for k in 1..<arr1.count {
 9                     ans = max(ans, arr1[k]*i + arr2[k]*j + k - best)
10                     best = min(best, arr1[k]*i + arr2[k]*j + k)
11                 }
12             }
13         }
14         return ans
15     }
16 }

224ms

 1 class Solution {
 2     func maxAbsValExpr(_ arr1: [Int], _ arr2: [Int]) -> Int {
 3         var res = 0
 4         var maxmm = Int.min
 5         var maxmp = Int.min
 6         var maxpm = Int.min
 7         var maxpp = Int.min
 8         
 9         var i = 0
10         while i < arr1.count {
11             maxmm = max(maxmm, -arr1[i] - arr2[i] - i)
12             maxmp = max(maxmp, -arr1[i] + arr2[i] - i)
13             maxpm = max(maxpm, arr1[i] - arr2[i] - i)
14             maxpp = max(maxpp, arr1[i] + arr2[i] - i)
15             res = max(res, maxmm + arr1[i] + arr2[i] + i)
16             res = max(res, maxmp + arr1[i] - arr2[i] + i)
17             res = max(res, maxpm - arr1[i] + arr2[i] + i)
18             res = max(res, maxpp - arr1[i] - arr2[i] + i)
19             
20             i += 1
21         }
22         
23         return res;
24     }
25 }

252ms

 1 class Solution {
 2     func maxAbsValExpr(_ arr1: [Int], _ arr2: [Int]) -> Int {
 3         var aux = [Int](repeating: 0, count: arr1.count)
 4         var result = Int.min
 5         for j in [-1, 1] {
 6             for k in [-1, 1] {
 7                 
 8                 for i in stride(from: 0, to: arr1.count, by: 1) {
 9                     aux[i] = arr1[i] * j + arr2[i] * k + i
10                 }
11                 let iPart = aux.max()!
12                 let jPart = aux.min()!
13                 result = max(result, iPart - jPart)
14             }
15         }
16         return result
17     }
18 }