一道算法题: 求一个数组中最大的 abs(max(left) - max(right))

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2808 天前的主题，其中的信息可能已经有所发展或是发生改变。

前几天碰到一道算法题, 由于限定时间感觉没有做好: 一个长度为 N 的数组 Arr, 可以按照其中的某个元素 K 做为分界点 0<=K<N, 得到其左边部分所有元素最大值(包括 K) 减去右边部分最大值(不包括 K)的绝对值 ABS. 需要写一个函数求助该数组中这个绝对值 ABS 最大是多少. 公式如下: max(abs(max{Arr_0, ... Arr_K} - max{Arr_K+1, ...Arr_N-1})) for K in (0...N-1)

要求写出时间 /空间复杂度均为 O(N)的算法, 但是我想了半天, 每次往右移动 K 取值的时候, 都要重新对右边的元素进行排序啊, 不知道怎么才能 O(N).

请教各位大神.

Max

ABS

数组

arr_k

58 条回复 • 2017-03-06 21:39:23 +08:00

dikcen

2017-03-03 20:44:48 +08:00

这个，不等于 max(Arr)-min(Arr)吗？

dikcen

2017-03-03 20:45:35 +08:00

错了，请无视

casparchen

2017-03-03 20:55:33 +08:00

就是 O （ n ）啊，先找到波峰，然后往后找波谷。

Dwayne

2017-03-03 20:57:26 +08:00 via iPhone

扫一次求最大值再扫一次求解也是 O(n) 吧

jky

2017-03-03 21:02:12 +08:00 via Android

顺序遍历计算并保留每个元素左边的最大值，然后逆序遍历计算最大值减去对应左边的最大值。

jonah

2017-03-03 21:03:33 +08:00 via Android

找到最大值，然后分别比较跟头尾之差哪个大，粗略想了一下。等下再细想

neosfung

2017-03-03 21:11:33 +08:00

建一个长度为 N 的数组 t_arr 。
第一轮是正向遍历， t_arr[i]表示的是，在 arr[0~i+1]中的最大值
第二轮是反向遍历，求 max(abs(max(arr[i+1 ~ N-1])), t_arr[i])

veryflying

2017-03-03 21:11:59 +08:00

假设原数组 arr,设两个辅助数组 a ， b ， a[i]表示 max(arr[0...i])， b[i]表示 max(arr[i...arr.length])，然后扫描一遍 a 和 b 就可以了，时间空间都是 O(n)。

xyzw

2017-03-03 21:13:54 +08:00 via iPhone

答案是 abs(max(arr) - min(arr[0], arr[N-1]))嗎？

neosfung

2017-03-03 21:14:51 +08:00

#7 下标标错了，不知道怎么改，希望楼主能理解

casparchen

2017-03-03 21:17:00 +08:00

@xyzw 不是。
首先，左边的最大数一定是数列中某一个波峰，但是不一定是最大的那个。所以记录当前最大波峰，然后动态更新最大差值就好。

veryflying

2017-03-03 21:17:31 +08:00

@veryflying 后来想一下，一个数组也可以。。

uoryon

2017-03-03 21:22:17 +08:00

@veryflying 嗯。确实。

ryd994

2017-03-03 21:39:15 +08:00 via Android

@jonah +1 每错就是这样
因为不论分界线是哪个：
1.如果全局 max 在分界线左，则右 max 大于左 max ，则左右 max 差取决于左 max 最小，反之同理
2. 从左向右移动分界线，左 max 单调递增，右 max 单调递减。反方向同理。
3. 因此分界线必定在两端之一，比较一下两端哪个小，和全局最大相减即可

ryd994

2017-03-03 21:40:53 +08:00 via Android

@casparchen 不对，最大数一定是全局最大，只不过最大 max 差可能是左减右或是右减左

eyp82

2017-03-03 21:44:42 +08:00

@casparchen 谢谢, 你的思路很好, 但感觉有个问题, 因为最后要求绝对值, 所以未必波峰-波谷就最大吧, 有可能左边比右边小, 得到一个很大的负数, 反而比波峰-波谷要大.

hd7771

2017-03-03 21:48:14 +08:00

从左往右扫，
这个时候分别维护一个最大值和一个最小值，
用当前的数与最大值和最小值差求 abs ，
更新答案，
更新最大值和最小值。

xyzw

2017-03-03 21:49:44 +08:00 via iPhone

@casparchen 假設最大數在分段 K 的左邊，結果是 max(arr) - max(arr[K..N-1])，小於等於 K=N-1 時的 max(arr) - arr[N-1]
假設最大數在分段時的右邊，結果是 abs(max(arr[0..K-1]) - max(arr))=max(arr) - max(arr[0..K-1])，小於等於 K=0 時的 max(arr) - arr[0]
要不 K=0 ，要不 K=N-1

hd7771

2017-03-03 21:50:43 +08:00

至于为什么维护最大值和最小值，你用贪心去反证。
如果我这个解最优那么比他小或者比他大是不是更好呢？没错就是更好。

eyp82

2017-03-03 21:54:12 +08:00

@jky
@neosfung

我想了一下你们的思路, 感觉你们是对的, 我当时没想到可以逆序遍历, 非常感谢.

nbndco

2017-03-03 21:55:45 +08:00 via iPhone

这个， leetcode 里面有吧，卖股票的……扫一遍就好了

ryd994

2017-03-03 22:00:35 +08:00 via Android

@hd7771 这是不对的
考虑 1 4 3 0 1
k=0 或 4
max 差为 3

hd7771

2017-03-03 22:09:46 +08:00

@ryd994 看错题目了
那就 left[i]保存前 i 个数最大值 right[i]保存 i~n 的最大值
答案就是遍历 i
ans = max(ans , abs(right[i + 1] - left[i]))

thekll

2017-03-03 22:13:24 +08:00 via iPhone

1 、分别找出[a_0,a_k]和(a_k,a_n-1]的最大值和最小值： a_lk_max,a_lk_min a_rk_max,a_rk_min.
2 、 max(k)=max(abs(a_lk_max-a_rk_min),abs(a_lk_min-a_rk_max);

hd7771

2017-03-03 22:13:41 +08:00

@ryd994 我就看了个标题就来答了。。

casparchen

2017-03-03 22:13:51 +08:00 via iPhone

@ryd994 哦，如果要求绝对值的话，结果一定是 max-min

casparchen

2017-03-03 22:17:24 +08:00 via iPhone

@casparchen 哦不对不对忽略我吧，已经被整晕

ryd994

2017-03-03 22:37:36 +08:00 via Android

可证 max(left)单调递增， max(right)单调递减
同时当 k=maxall 的下标， max(left)=max(right)=max (all)
因此答案一定是 max(all)-第一个或者 max(all)-最后一个
各位请看我 14 楼

@casparchen
@hd7771
@thekll

thekll

2017-03-03 22:56:48 +08:00 via iPhone

3 、将 k 从 0 到 n-1 的 max(k)产生的数组排序，得到 max 以及对应的 k 值。

shibingsw

2017-03-03 22:58:27 +08:00

@ryd994 你是对的

thekll

2017-03-03 23:11:10 +08:00 via iPhone

上面的 1 、 2 步改为只计算最大值及最大值之差的绝对值。

holyghost

2017-03-04 00:04:57 +08:00 via iPhone

感觉 28 楼应该是最合理的答案了， O(n)的时间复杂度和 O(1 的空间复杂度)。

另外楼主是在哪里看到的题目呢？谢谢。

deljuven

2017-03-04 00:27:36 +08:00

先开一个长度为 n 的数组，从头开始数，第 i 位就是 i 左边的最大值；然后从尾开始数，得到第 i 位右边的最大值，同时将第一个数组的第 i 位减去求 abs ，得到当前的最大值。遍历结束就可以得到最终的最大值，一共遍历两次，消耗了 n 的空间。
这是我想到的算法……

deljuven

2017-03-04 00:41:33 +08:00

7 楼正解……确实只要比较最大值和两个端点的差然后求最大值就可以了。这样一次遍历+常数空间就解决了……

daozhihun

2017-03-04 00:46:44 +08:00 via Android

先 k 为 0 扫一边，左边最大右边最小知道了，然后逐个右移，判断是否要更新左最大和右最小。取差值最大的一个即可。当然题目是绝对值，所以要反过来再扫一边。
感觉空间可以常数。

jonah

2017-03-04 00:51:57 +08:00 via Android

@daozhihun 不是左最大右最小，是两个最大之差

daozhihun

2017-03-04 00:52:56 +08:00 via Android

@jonah 刚发现了，看错题了 😂

ryd994

2017-03-04 07:28:33 +08:00 via Android

楼主你公式错了：
按 Python 写法
对于某数组 a 长度 n
求 max( [abs(max(a[0:K])-max(a[K:-1])) for K in range(n)] )

ryd994

2017-03-04 07:29:04 +08:00 via Android

哦不：
max( [abs(max(a[:K])-max(a[K:])) for K in range(n)] )

ryd994

2017-03-04 07:30:17 +08:00 via Android

哦还是不
这样当 K=N-1 的时候右边岂不是空了？
max( [abs(max(a[:K])-max(a[K:])) for K in range(n-1)] )

ryd994

2017-03-04 07:32:43 +08:00 via Android

md 我大概今天脑子冻傻了
slice 右边开区间
max( [abs(max(a[:K+1])-max(a[K+1:])) for K in range(n-1)] )

juxingzhutou

2017-03-04 08:50:38 +08:00

1. 先正向遍历一遍 Arr ，求出一个长度为 N 的数组 asc ， asc = {n | n = max{Arr[0..k]}, k∈[0..N-1), k∈N(自然数)}， asx[i]就等于 Arr[0..i]中的最大值
2. 再反向遍历一遍 Arr ，求出一个长度为 N 的数组 desc ， desc = {n | n = max{Arr[k..N-1]}, k∈(0..N], k∈N(自然数)}， desc[i]就等于 Arr[i+1..N-1]中的最大值
3. 遍历 i in range(0..N-2)，找出 abs(asc[i] - desc[i])的最大值

算法复杂度 3n ，符合你 O(n)的要求。

优化：步骤 2 和步骤 3 可以合并在一起，不用单独创建一个数组 desc

bidongliang

2017-03-04 09:14:24 +08:00 via Android

这个值在交易中叫最大回撤， O(n)算法，从后向前扫描，维护当前看到的最小值和扫描位置元素与当前最小值的差，结果就是所求。

random123

2017-03-04 10:16:54 +08:00

@jonah
@jky
@neosfung
@veryflying
@xyzw
@ryd994

如果没猜错的话, 楼主名字的简写是 ZX, 我是原来安排的面试官之一. 我们很喜欢好学的人, 如果是你的话, 我会和别的 team 再讨论一下你的简历.

另外这道题我自己当时做也是#7 的解法, 但其实觉得逆序遍历才更符合计算机的思维, 更普适. 我回复的这几位如果想去外资 IT 工作的话可以留下邮箱地址, 我来安排面试, 我们提供一流的薪水, 期权和办公环境, 顶配 rMBP, Apple 外接显示器, 不加班. 尤其欢迎有数据库核心开发经验和喜欢敏捷开发的朋友. 工作地点在北京中关村.

AlisaDestiny

2017-03-04 10:22:17 +08:00

你求最大值不一定要排序吧。用变量记录一下就好。移动 K 的时候比较下记录与新值的大小。

liprais

2017-03-04 10:25:14 +08:00

这是 pivotal 的面试题吧

LukeEuler

2017-03-04 10:42:47 +08:00

@ryd994 正解。而且空间复杂度是 O(1)

hanzichi

2017-03-04 10:45:51 +08:00

遍历的时候，可以得到前 n 个的最值，那么，反向遍历的时候，同样可以得到后 n 个的最值。。

其实再不济， ST 预处理下， O （ nlogn ）也能解。。 https://github.com/hanzichi/algorithm-js/blob/master/RMQ-ST.js

hst001

2017-03-04 12:00:45 +08:00 via Android

@casparchen 不一定是波峰

ryd994

2017-03-04 13:09:47 +08:00 via Android

@random123 一脸懵哔，我只是个还没毕业应届而已啊

ryd994

2017-03-04 13:15:42 +08:00 via Android

@juxingzhutou
@hanzichi
想到这里很不错，但是再往前一步
请看我 28 楼
最小 max 一定在两端
其他地方可能存在相等，不可能更优

hanzichi

2017-03-04 13:44:18 +08:00

@ryd994 #51 666 这波可以

jky

2017-03-04 14:11:34 +08:00 via Android

@random123 谢谢，不过目前没有换工作的计划:P 。

juxingzhutou

2017-03-04 14:12:56 +08:00

@ryd994 恩，你这个解法确实更好，可以优化常系数。

juxingzhutou

2017-03-04 14:16:55 +08:00

@bidongliang 最大回撤不是这个意思，最大回撤是选的最大跌幅区间，是(最大值 - 最小值)最大的区间。

uucloud

2017-03-04 17:09:15 +08:00

确实。。第一反应是#5 楼的解法扫两遍，不过#14 的解法更巧妙，只扫一遍就好。

popbones

2017-03-05 13:16:35 +08:00

不知道我是否理解了题目。

是要求所有可能的分割中最大的子串最大值的绝对差吗？

因为分两段，其中一段的最大值肯定是全局最大值，另一段的最大值一定大于等于这一段的两个端点值中的最小值

为了让第二段最小，则设第二段的大小为 1 ，所以第二段要么是数组的第一个值，要么是数组的最后一个值，因为包含更多的值只会增大这一段的最大值或对这一段的最大值没有影响。

这样的话就扫一遍得出全局最大，跟两个断电比一下，然后几个 if-elas 就好了 https://play.golang.org/p/1IpfFujqfh

justyy

2017-03-06 21:39:23 +08:00

这 C++题解在这里: https://helloacm.com/an-interview-question-on-algorithm-to-find-absmax-left-max-right/