解题思路

关键定义

一个数组的“波动值”就是排序后相邻元素差的最小值（若元素全相同或个数不足 2，则为 0）。因此，删除一个元素后，新的波动值等于删后数组中相邻差的最小值。

观察与转化

将数组升序为 a[0..n-1]，相邻差为 d[i] = a[i+1] - a[i] (i = 0..n-2)。

题目内容

给定一个整数数组 $nums$ ，定义“波动值”为：

• 若数组中存在至少两个值不同的元素，波动值是这些元素中任意两个的差的绝对值的最小值；

• 若数组中所有元素值相同，或数组长度小于 $2$ (不足两个元素)，波动值为 $0$ 。

要求必须删除且仅删除数组中的一个元素，使剩余数组的波动值尽可能大。请输出这个最大可能的波动值。

输入描述

• 第一行一个整数 n，表示数组长度（1 ≤ n ≤ 10^7）。
• 第二行输入 n 个整数，表示数组元素。

输出描述

输出一个整数，表示删除恰好一个元素后，剩余数组可能的最大波动值。

样例1

输入

4
4 2 8 1

输出

3

说明

原数组中，不同元素的最小差为 $1(2$ 和 $1$ 的差)。删除元素 $2$ 后，剩余数组 $[4,8,1]$ 的波动值为 $3(4$ 和 $1$ 的差)，这是所有删除操作中的最大值。

样例2

输入

3
1 2 1

输出

1

说明

删除任意一个 $1$ 后，剩余数组 $[1,2]$ 或 $[2,1]$ 的波动值为 $1$ ;删除 $2$ 后，剩余数组 $[1,1]$ 的波动值为 $0$ 。最大波动值为 $1$ 。

样例3

输入

3
5 5 5

输出

0

说明

无论删除哪个元素，剩余数组均为 $[5,5]$ (元素全相同)，波动值为 $0$ 。