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

[eyp82]

前几天碰到一道算法题, 由于限定时间感觉没有做好: 一个长度为 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).

请教各位大神.

[nbndco]

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

[ryd994]

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

[hd7771]

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

[thekll]

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]

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

[casparchen]

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

[casparchen]

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

[ryd994]

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

@casparchen
@hd7771
@thekll

[thekll]

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

[shibingsw]

@ryd994 你是对的

[thekll]

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

[holyghost]

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


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

[deljuven]

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

[deljuven]

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

[daozhihun]

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

[jonah]

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

[daozhihun]

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

[ryd994]

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

[ryd994]

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

[ryd994]

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