题解 | #最大差值_4循环双指针优化#

我以为是动态规划，但是思考没有得出好的思路，想其他优化路径，比如，如果左边遍历发现下一位已经比前一位小了，那必然A[i]-A[j]>A[i+1]-A[j]。然后用一个while移动到A[i]<A[i+n]，避免不必要的遍历。此时，已经过了，可以使用注释的代码。然后我又思考了，右边优化，就又快一点了。

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param n int整型 
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        int res = 0;
        
        int left = 0;
        
        int right = 0;
        
        for(int i=0;i<=n-2;i++)
        {
            while(i>0&&i<=n-2&&left<A[i]) i++;
            
            left = A[i];
            
            //
            for(int j=n-1;j>i;j--)
            {
                while(j<n-1&&j>i&&right>A[j]) j--;
                
                right = A[j];
                
                res = max(res,A[j]-A[i]);
            }
            //
            
            /*
            for(int j=i+1;j<=n-1;j++)
            {
                res = max(res,A[j]-A[i]);
            }
            */
        }
            return res;
            
    }
};