题目

题目很是简单，基本如题，如何最小成本的求数组中最大值和最小值

思路 & 代码

思路一

最简单最直接的，弄两个临时变量，走一遍，存最大和最小的，时间复杂度 2*N（不是N啊，每个元素你要比较两次的）

思路二

想都不用想上面的不能满足我们，这个问题不是多么复杂高端的问题，直觉上或许分治法是个解决办法

• 我们把数组奇数位和偶数位分开成两个数组
• 首先比较相邻两者大小，之后，最小值只用在小的一边去找，比如可以统一把两者较小的放到奇数位
• 遍历奇数位数组，寻找最小值
• 遍历偶数位数组，寻找最大值
  如此，已经简单了一些了，复杂度为1.5N。
  这种方式可以，不过强迫症同学可能会说，敢不敢不破坏原有数组呢？

思路三

上面那么说，那必须能那么做，不然广大风华绝代的程序大佬多没面子
破坏原有数组，是为了遍历长度变短，那我们换个思路，可以把步子迈大一些啊！
每次走两格，两个元素先比较，然后大的去跟最大值缓存比较，小的跟最小值缓存比较，ok了，不破坏原有数组的1.5N

思路四

我们思路二和三都是二分法，已经有效减小复杂度了，那我们上无限分治，能不能继续提高呢？
来个伪代码

(max, min) search(arr, start, end)
{
    if (end - start <= 1) {
        if (arr[start] < arr[end])
            return (arr[end], arr[start]);
        else 
            return (arr[start], arr[end]);
    }

    (maxL, minL) = search(arr, start, (start + (end - start) / 2));
    (maxR, minR) = search(arr, (start + (end - start) / 2) + 1, end);

    if (maxL > maxR)
        maxV = maxL
    else 
        maxV = maxR

    if (minL < minR)
        minV = minL
    else 
        minV = minR

    return (maxV, minV);
}

大家可以试试算下这个复杂度，其实，差不多1.5N（书上给出是1.5N - 2），那么其实来说，就相当于没有什么提升了

拓展思考

如果要找出数组中的第二大数，怎么办？
应该是分治思路即可，没想到其他的办法，有大手子有更好的望指点

思考

一顿操作不一定有用，不要迷信方法论，实践出真知

以上，欢迎大家指点、交流。

---

欢迎大家关注我的公众号

半亩房顶