当前位置: 代码迷 >> 综合 >> [leetcode每日一题]1131.绝对值表达式的最大值
  详细解决方案

[leetcode每日一题]1131.绝对值表达式的最大值

热度:63   发布时间:2023-11-19 23:55:08.0

描述:

  可以发现这是求一个【最长】三维的曼哈顿距离,首先考虑二维的情况,有两个点(x1,y1) 和(x2,y2),此时求的是 

  |x1-x2|+|y1-y2|最大值,也就是这四者的最大值:

x1-x2+y1-y2 

x1-x2+y2-y1

x2-x1+y1-y2

x2-x1+y2-y1

转换一下顺序:

x1+y1 - (x2+y2)

x1-y1 +(x2-y2)

-x1+y1-(-x2+y2)

-x1-y1+(-x2-y2) 

也就是说前后的运算符号是一样的。

再来看三维的情况:  设求的是(onei,twoi,i )和(onej,twoj,j) 之间的最大曼哈顿距离,这里的one是arr1,two是arr2 ,一共有2*2*2=8种可能:

onei+twoi+i-(onej+twoj+j)

onei+twoi-i-(onej+twoj-j)

onei-twoi+i-(onej-twoj+j)

onei-twoi-i-(onej-twoj-j)

 

-onei+twoi+i-(-onej+twoj+j)

-onei+twoi-i-(-onej+twoj-j)

-onei-twoi+i-(-onej-twoj+j)

-onei-twoi-i-(-onej-twoj-j)

本题对i,j的大小没有限制,也就是说onei+twoi+i可以和onej+twoj+j互换,此时要求最大曼哈顿距离,只要求这8种情况的最大值

max(

max(onei+twoi+i-(onej+twoj+j))

max(onei+twoi-i-(onej+twoj-j))

)

可以看到复杂度是8*arr1.length

那么怎么求每一次的最大值呢,做法就是求最大的onei+twoi+i ,减去最小的onei+twoi+i

题解如下