题解 | 两种方法轻松教你解决 #左右最值最大差#

class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
       int ma = A[0];
       for(auto e : A)
           ma = max(ma, e);
        return max(ma - A.front(), ma - A.back());
    }
};

先讲思路 找到最大值然后直接比较最大值和左右端点值的差， 找出最大值即可

证明 ：

首先我们找到的最大值已经确定了我们需要选择的某一个区间

证明：

答案为左右两个区间的最大值的差， 那么作为数组的最大值， 无论怎么分都会成为某一个区间的最大值

接下来我们分析另外一个区间：

首先我们分析右端点 发现只有两种情况

1. 右端点 > 右端点到最大值之间的数
2. 右端点 < 右端点到最大值之间的数

对于第一种情况 如果我们将区间扩大 即不只包含右端点 那么会发现无论怎么改变该区间的最大值一定为右端点（因为到最大值之间右端点的值是最大的）

对于第二种情况 如果我们将端点扩张 那么一定会导致该区间的最大值变大 使得最大值 减 该区间的最大值的差减小 不符和题目求

对于左端点同理

综上 ： 另一个区间一定为左右端点中的某一个端点

特别的 当最大值为左右端点中的某一个时 由于自己减去自己为0 一定小于自己减去另一个端点， 所以不需要特判

class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
        vector<int> rma(A.size());
        for (int i = A.size() - 1, ma = -0x3f3f3f3f; i >= 0; -- i)
            ma = max(ma, A[i]), rma[i] = ma;
        int res = 0;
        for (int i = 1, ma = A[0]; i < A.size(); ++ i) {
            res = max(res, abs(ma - rma[i]));
            ma = max(ma, A[i]);
        }
        return res;
    }
};

我们直接存储每个点到右端点之间的最大值 然后遍历数组的同时算右端点的最大值 最后边遍历边找出答案

两种方法都是O(n)的，也许第一个代码量确实比较小，思维也更巧妙 但是还是那句话 能做对题目的算法就是好算法