V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
eyp82
V2EX  ›  程序员

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

  •  
  •   eyp82 · 2017-03-03 20:28:39 +08:00 · 6724 次点击
    这是一个创建于 2806 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    请教各位大神.

    58 条回复    2017-03-06 21:39:23 +08:00
    dikcen
        1
    dikcen  
       2017-03-03 20:44:48 +08:00
    这个,不等于 max(Arr)-min(Arr)吗?
    dikcen
        2
    dikcen  
       2017-03-03 20:45:35 +08:00
    错了,请无视
    casparchen
        3
    casparchen  
       2017-03-03 20:55:33 +08:00
    就是 O ( n )啊,先找到波峰,然后往后找波谷。
    Dwayne
        4
    Dwayne  
       2017-03-03 20:57:26 +08:00 via iPhone
    扫一次求最大值 再扫一次求解也是 O(n) 吧
    jky
        5
    jky  
       2017-03-03 21:02:12 +08:00 via Android   ❤️ 1
    顺序遍历计算并保留每个元素左边的最大值,然后逆序遍历计算最大值减去对应左边的最大值。
    jonah
        6
    jonah  
       2017-03-03 21:03:33 +08:00 via Android
    找到最大值,然后分别比较跟头尾之差哪个大,粗略想了一下。等下再细想
    neosfung
        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])
    veryflying
        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)。
    xyzw
        9
    xyzw  
       2017-03-03 21:13:54 +08:00 via iPhone
    答案是 abs(max(arr) - min(arr[0], arr[N-1]))嗎?
    neosfung
        10
    neosfung  
       2017-03-03 21:14:51 +08:00
    #7 下标标错了,不知道怎么改,希望楼主能理解
    casparchen
        11
    casparchen  
       2017-03-03 21:17:00 +08:00
    @xyzw 不是。
    首先,左边的最大数一定是数列中某一个波峰,但是不一定是最大的那个。所以记录当前最大波峰,然后动态更新最大差值就好。
    veryflying
        12
    veryflying  
       2017-03-03 21:17:31 +08:00
    @veryflying 后来想一下,一个数组也可以。。
    uoryon
        13
    uoryon  
       2017-03-03 21:22:17 +08:00
    @veryflying 嗯。确实。
    ryd994
        14
    ryd994  
       2017-03-03 21:39:15 +08:00 via Android
    @jonah +1 每错就是这样
    因为不论分界线是哪个:
    1.如果全局 max 在分界线左,则右 max 大于左 max ,则左右 max 差取决于左 max 最小,反之同理
    2. 从左向右移动分界线,左 max 单调递增,右 max 单调递减。反方向同理。
    3. 因此分界线必定在两端之一,比较一下两端哪个小,和全局最大相减即可
    ryd994
        15
    ryd994  
       2017-03-03 21:40:53 +08:00 via Android
    @casparchen 不对,最大数一定是全局最大,只不过最大 max 差可能是左减右或是右减左
    eyp82
        16
    eyp82  
    OP
       2017-03-03 21:44:42 +08:00
    @casparchen 谢谢, 你的思路很好, 但感觉有个问题, 因为最后要求绝对值, 所以未必波峰-波谷就最大吧, 有可能左边比右边小, 得到一个很大的负数, 反而比波峰-波谷要大.
    hd7771
        17
    hd7771  
       2017-03-03 21:48:14 +08:00
    从左往右扫,
    这个时候分别维护一个最大值和一个最小值,
    用当前的数与最大值和最小值差求 abs ,
    更新答案,
    更新最大值和最小值。
    xyzw
        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
    hd7771
        19
    hd7771  
       2017-03-03 21:50:43 +08:00
    至于为什么维护最大值和最小值,你用贪心去反证。
    如果我这个解最优那么比他小或者比他大是不是更好呢?没错就是更好。
    eyp82
        20
    eyp82  
    OP
       2017-03-03 21:54:12 +08:00
    @jky
    @neosfung

    我想了一下你们的思路, 感觉你们是对的, 我当时没想到可以逆序遍历, 非常感谢.
    nbndco
        21
    nbndco  
       2017-03-03 21:55:45 +08:00 via iPhone
    这个, leetcode 里面有吧,卖股票的……扫一遍就好了
    ryd994
        22
    ryd994  
       2017-03-03 22:00:35 +08:00 via Android
    @hd7771 这是不对的
    考虑 1 4 3 0 1
    k=0 或 4
    max 差为 3
    hd7771
        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]))
    thekll
        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);
    hd7771
        25
    hd7771  
       2017-03-03 22:13:41 +08:00
    @ryd994 我就看了个标题就来答了。。
    casparchen
        26
    casparchen  
       2017-03-03 22:13:51 +08:00 via iPhone
    @ryd994 哦,如果要求绝对值的话,结果一定是 max-min
    casparchen
        27
    casparchen  
       2017-03-03 22:17:24 +08:00 via iPhone
    @casparchen 哦不对不对忽略我吧,已经被整晕
    ryd994
        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
    thekll
        29
    thekll  
       2017-03-03 22:56:48 +08:00 via iPhone
    3 、将 k 从 0 到 n-1 的 max(k)产生的数组排序,得到 max 以及对应的 k 值。
    shibingsw
        30
    shibingsw  
       2017-03-03 22:58:27 +08:00
    @ryd994 你是对的
    thekll
        31
    thekll  
       2017-03-03 23:11:10 +08:00 via iPhone
    上面的 1 、 2 步改为只计算最大值及最大值之差的绝对值。
    holyghost
        32
    holyghost  
       2017-03-04 00:04:57 +08:00 via iPhone
    感觉 28 楼应该是最合理的答案了, O(n)的时间复杂度和 O(1 的空间复杂度)。


    另外楼主是在哪里看到的题目呢?谢谢。
    deljuven
        33
    deljuven  
       2017-03-04 00:27:36 +08:00
    先开一个长度为 n 的数组,从头开始数,第 i 位就是 i 左边的最大值;然后从尾开始数,得到第 i 位右边的最大值,同时将第一个数组的第 i 位减去求 abs ,得到当前的最大值。遍历结束就可以得到最终的最大值,一共遍历两次,消耗了 n 的空间。
    这是我想到的算法……
    deljuven
        34
    deljuven  
       2017-03-04 00:41:33 +08:00
    7 楼正解……确实只要比较最大值和两个端点的差然后求最大值就可以了。这样一次遍历+常数空间就解决了……
    daozhihun
        35
    daozhihun  
       2017-03-04 00:46:44 +08:00 via Android
    先 k 为 0 扫一边,左边最大右边最小知道了,然后逐个右移,判断是否要更新左最大和右最小。取差值最大的一个即可。当然题目是绝对值,所以要反过来再扫一边。
    感觉空间可以常数。
    jonah
        36
    jonah  
       2017-03-04 00:51:57 +08:00 via Android
    @daozhihun 不是左最大右最小,是两个最大之差
    daozhihun
        37
    daozhihun  
       2017-03-04 00:52:56 +08:00 via Android
    @jonah 刚发现了,看错题了 😂
    ryd994
        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)] )
    ryd994
        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)] )
    ryd994
        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)] )
    ryd994
        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)] )
    juxingzhutou
        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
    bidongliang
        43
    bidongliang  
       2017-03-04 09:14:24 +08:00 via Android
    这个值在交易中叫最大回撤, O(n)算法,从后向前扫描,维护当前看到的最小值和扫描位置元素与当前最小值的差,结果就是所求。
    random123
        44
    random123  
       2017-03-04 10:16:54 +08:00
    @jonah
    @jky
    @neosfung
    @veryflying
    @xyzw
    @ryd994

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

    另外这道题我自己当时做也是#7 的解法, 但其实觉得逆序遍历才更符合计算机的思维, 更普适. 我回复的这几位如果想去外资 IT 工作的话可以留下邮箱地址, 我来安排面试, 我们提供一流的薪水, 期权和办公环境, 顶配 rMBP, Apple 外接显示器, 不加班. 尤其欢迎有数据库核心开发经验和喜欢敏捷开发的朋友. 工作地点在北京中关村.
    AlisaDestiny
        45
    AlisaDestiny  
       2017-03-04 10:22:17 +08:00
    你求最大值不一定要排序吧。用变量记录一下就好。移动 K 的时候比较下记录与新值的大小。
    liprais
        46
    liprais  
       2017-03-04 10:25:14 +08:00
    这是 pivotal 的面试题吧
    LukeEuler
        47
    LukeEuler  
       2017-03-04 10:42:47 +08:00
    @ryd994 正解。而且空间复杂度是 O(1)
    hanzichi
        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
    hst001
        49
    hst001  
       2017-03-04 12:00:45 +08:00 via Android
    @casparchen 不一定是波峰
    ryd994
        50
    ryd994  
       2017-03-04 13:09:47 +08:00 via Android
    @random123 一脸懵哔,我只是个还没毕业应届而已啊
    ryd994
        51
    ryd994  
       2017-03-04 13:15:42 +08:00 via Android   ❤️ 1
    @juxingzhutou
    @hanzichi
    想到这里很不错,但是再往前一步
    请看我 28 楼
    最小 max 一定在两端
    其他地方可能存在相等,不可能更优
    hanzichi
        52
    hanzichi  
       2017-03-04 13:44:18 +08:00
    @ryd994 #51 666 这波可以
    jky
        53
    jky  
       2017-03-04 14:11:34 +08:00 via Android
    @random123 谢谢,不过目前没有换工作的计划:P 。
    juxingzhutou
        54
    juxingzhutou  
       2017-03-04 14:12:56 +08:00
    @ryd994 恩,你这个解法确实更好,可以优化常系数。
    juxingzhutou
        55
    juxingzhutou  
       2017-03-04 14:16:55 +08:00
    @bidongliang 最大回撤不是这个意思,最大回撤是选的最大跌幅区间,是(最大值 - 最小值)最大的区间。
    uucloud
        56
    uucloud  
       2017-03-04 17:09:15 +08:00
    确实。。第一反应是#5 楼的解法扫两遍,不过#14 的解法更巧妙,只扫一遍就好。
    popbones
        57
    popbones  
       2017-03-05 13:16:35 +08:00
    不知道我是否理解了题目。

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

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

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

    这样的话就扫一遍得出全局最大,跟两个断电比一下,然后几个 if-elas 就好了 https://play.golang.org/p/1IpfFujqfh
    justyy
        58
    justyy  
       2017-03-06 21:39:23 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1040 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 81ms · UTC 19:51 · PVG 03:51 · LAX 11:51 · JFK 14:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.