这是一个创建于 3146 天前的主题，其中的信息可能已经有所发展或是发生改变。
前几天碰到一道算法题, 由于限定时间感觉没有做好: 一个长度为 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).
请教各位大神.
 | 1 dikcen 2017-03-03 20:44:48 +08:00 这个，不等于 max(Arr)-min(Arr)吗？ |
| 2 dikcen 2017-03-03 20:45:35 +08:00 错了，请无视 |
 | 3 casparchen 2017-03-03 20:55:33 +08:00 就是 O （ n ）啊，先找到波峰，然后往后找波谷。 |
 | 4 Dwayne 2017-03-03 20:57:26 +08:00 via iPhone 扫一次求最大值 再扫一次求解也是 O(n) 吧 |
 | 5 jky 2017-03-03 21:02:12 +08:00 via Android  1 顺序遍历计算并保留每个元素左边的最大值，然后逆序遍历计算最大值减去对应左边的最大值。 |
 | 6 jonah 2017-03-03 21:03:33 +08:00 via Android 找到最大值，然后分别比较跟头尾之差哪个大，粗略想了一下。等下再细想 |
 | 7 neosfung 2017-03-03 21:11:33 +08:00 2 建一个长度为 N 的数组 t_arr 。 第一轮是正向遍历， t_arr[i]表示的是，在 arr[0~i+1]中的最大值 第二轮是反向遍历，求 max(abs(max(arr[i+1 ~ N-1])), t_arr[i]) |
 | 8 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)。 |
 | 9 xyzw 2017-03-03 21:13:54 +08:00 via iPhone 答案是 abs(max(arr) - min(arr[0], arr[N-1]))？ |
| 10 neosfung 2017-03-03 21:14:51 +08:00 #7 下标标错了，不知道怎么改，希望楼主能理解 |
| 11 casparchen 2017-03-03 21:17:00 +08:00 @xyzw 不是。 首先，左边的最大数一定是数列中某一个波峰，但是不一定是最大的那个。所以记录当前最大波峰，然后动态更新最大差值就好。 |
| 12 veryflying 2017-03-03 21:17:31 +08:00 @veryflying 后来想一下，一个数组也可以。。 |
 | 13 uoryon 2017-03-03 21:22:17 +08:00 @veryflying 嗯。确实。 |
 | 14 ryd994 2017-03-03 2139:15 +08:00 via Android @jonah +1 每错就是这样 因为不论分界线是哪个： 1.如果全局 max 在分界线左，则右 max 大于左 max ，则左右 max 差取决于左 max 最小，反之同理 2. 从左向右移动分界线，左 max 单调递增，右 max 单调递减。反方向同理。 3. 因此分界线必定在两端之一，比较一下两端哪个小，和全局最大相减即可 |
| 15 ryd994 2017-03-03 21:40:53 +08:00 via Android @casparchen 不对，最大数一定是全局最大，只不过最大 max 差可能是左减右或是右减左 |
 | 16 eyp82 OP @casparchen 谢谢, 你的思路很好, 但感觉有个问题, 因为最后要求绝对值, 所以未必波峰-波谷就最大吧, 有可能左边比右边小, 得到一个很大的负数, 反而比波峰-波谷要大. |
 | 17 hd7771 2017-03-03 21:48:14 +08:00 从左往右扫， 这个时候分别维护一个最大值和一个最小值， 用当前的数与最大值和最小值差求 abs ， 更新答案， 更新最大值和最小值。 |
| 18 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 |
| 19 hd7771 2017-03-03 21:50:43 +08:00 至于为什么维护最大值和最小值，你用贪心去反证。 如果我这个解最优那么比他小或者比他大是不是更好呢？没错就是更好。 |
 | 21 nbndco 2017-03-03 21:55:45 +08:00 via iPhone 这个， leetcode 里面有吧，卖股票的…扫一遍就好了 |
| 23 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])) |
 | 24 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); |
| 26 casparchen 2017-03-03 22:13:51 +08:00 via iPhone @ryd994 哦，如果要求绝对值的话，结果一定是 max-min |
| 27 casparchen 2017-03-03 22:17:24 +08:00 via iPhone @casparchen 哦不对不对忽略我吧，已经被整晕 |
| 28 ryd994 2017-03-03 22:37:36 +08:00 via Android 6 可证 max(left)单调递增， max(right)单调递减 同时当 k=maxall 的下标， max(left)=max(right)=max (all) 因此答案一定是 max(all)-第一个或者 max(all)-最后一个 各位请看我 14 楼 @casparchen @hd7771 @thekll |
| 29 thekll 2017-03-03 22:56:48 +08:00 via iPhone 3 、将 k 从 0 到 n-1 的 max(k)产生的数组排序，得到 max 以及对应的 k 值。 |
| 31 thekll 2017-03-03 23:11:10 +08:00 via iPhone 上面的 1 、 2 步改为只计算最大值及最大值之差的绝对值。 |
 | 32 holyghost 2017-03-04 00:04:57 +08:00 via iPhone 感觉 28 楼应该是最合理的答案了， O(n)的时间复杂度和 O(1 的空间复杂度)。 另外楼主是在哪里看到的题目呢？谢谢。 |
 | 33 deljuven 2017-03-04 00:27:36 +08:00 先开一个长度为 n 的数组，从头开始数，第 i 位就是 i 左边的最大值；然后从尾开始数，得到第 i 位右边的最大值，同时将第一个数组的第 i 位减去求 abs ，得到当前的最大值。遍历结束就可以得到最终的最大值，一共遍历两次，消耗了 n 的空间。 这是我想到的算法…… |
| 34 deljuven 2017-03-04 00:41:33 +08:00 7 楼正解……确实只要比较最大值和两个端点的差然后求最大值就可以了。这样一次遍历+常数空间就解决了…… |
 | 35 daozhihun 2017-03-04 00:46:44 +08:00 via Android 先 k 为 0 扫一边，左边最大右边最小知道了，然后逐个右移，判断是否要更新左最大和右最小。取差值最大的一个即可。当然题目是绝对值，所以要反过来再扫一边。 感觉空间可以常数。 |
| 38 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)] ) |
| 39 ryd994 2017-03-04 07:29:04 +08:00 via Android 哦不： max( [abs(max(a[:K])-max(a[K:])) for K in range(n)] ) |
| 40 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)] ) |
| 41 ryd994 2017-03-04 07:32:43 +08:00 via Android 1 md 我大概今天脑子冻傻了 slice 右边开区间 max( [abs(max(a[:K+1])-max(a[K+1:])) for K in range(n-1)] ) |
 | 42 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 |
 | 43 bidongliang 2017-03-04 09:14:24 +08:00 via Android 这个值在交易中叫最大回撤， O(n)算法，从后向前扫描，维护当前看到的最小值和扫描位置元素与当前最小值的差，结果就是所求。 |
 | 44 random123 2017-03-04 10:16:54 +08:00 |
 | 45 AlisaDestiny 2017-03-04 10:22:17 +08:00 你求最大值不一定要排序吧。用变量记录一下就好。移动 K 的时候比较下记录与新值的大小。 |
 | 46 F281M6Dh8DXpD1g2 2017-03-04 10:25:14 +08:00 这是 pivotal 的面试题吧 |
 | 48 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 |
 | 49 hst001 2017-03-04 12:00:45 +08:00 via Android @casparchen 不一定是波峰 |
| 51 ryd994 2017-03-04 13:15:42 +08:00 via Android 1 |
| 54 juxingzhutou 2017-03-04 14:12:56 +08:00 @ryd994 恩，你这个解法确实更好，可以优化常系数。 |
| 55 juxingzhutou 2017-03-04 14:16:55 +08:00 @bidongliang 最大回撤不是这个意思，最大回撤是选的最大跌幅区间，是(最大值 - 最小值)最大的区间。 |
 | 56 uucloud 2017-03-04 17:09:15 +08:00 确实。。第一反应是#5 楼的解法扫两遍，不过#14 的解法更巧妙，只扫一遍就好。 |
 | 57 popbones 2017-03-05 13:16:35 +08:00 不知道我是否理解了题目。 是要求所有可能的分割中最大的子串最大值的绝对差吗？ 因为分两段，其中一段的最大值肯定是全局最大值，另一段的最大值一定大于等于这一段的两个端点值中的最小值 为了让第二段最小，则设第二段的大小为 1 ，所以第二段要么是数组的第一个值，要么是数组的最后一个值，因为包含更多的值只会增大这一段的最大值或对这一段的最大值没有影响。 这样的话就扫一遍得出全局最大，跟两个断电比一下，然后几个 if-elas 就好了 https://playgolang.org/p/1IpfFujqfh |
 | 58 justyy 2017-03-06 21:39:23 +08:00 |
Select Language