最大差值

[编程题]最大差值

热度指数：1633 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个未排序的数列，找到此数列在已排序状态下的两个相邻值的最大差值，少于两个值时返回0。例如：给定数列 [1,3,2,0,1,6,8] 则最大差值为3。注意：请尽量使用时间复杂度为O(n)的方案。

输入描述:

第一行输入单个整数N作为数列的大小，第二行输入所有数列中的元素M，共N个。0 < N <= 1000000, 0 < M < 2100000000

输出描述:

数列的最大差值

示例1

输入

3
1 10 5

输出

算法知识视频讲解

Java

牛客150138644号

第三组测试数据有问题

发表于 2023-08-30 09:43:20 回复(0)

Java

开心超人129267

public class LongestDistance {

    public int getDis(int[] A, int n) {
        // 定义两个数组, leftMin 和 rightMax, 其中 leftMin[i] 表示从 0 到 i 之间的最小值,
        // rightMax[i] 表示从 n-1 到 i 之间的最大值.
        // 之后利用 rightMax[i] - leftMin[i] 得到差的最大值

        int[] leftMin = new int[n];
        int[] rightMax = new int[n];
        leftMin[0] = A[0];
        rightMax[n - 1] = A[n - 1];

        for (int i = 1; i < n; ++i) {
            if (leftMin[i - 1] < A[i]) {
                leftMin[i] = leftMin[i - 1];
            } else {
                leftMin[i] = A[i];
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (rightMax[i + 1] > A[i]) {
                rightMax[i] = rightMax[i + 1];
            } else {
                rightMax[i] = A[i];
            }
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (rightMax[i] - leftMin[i] > res) {
                res = rightMax[i] - leftMin[i];
            }
        }
        return res;
    }
}

发表于 2018-09-06 08:45:14 回复(0)