数组是 1..n 的排列,数值连续的数对只有 (1,2),(2,3),…,(n−1,n) 共 n−1 对。
因此只需记录每个值出现的下标 pos[v],再对每个 v=1..n−1 计算 ∣pos[v]−pos[v+1]∣,取最大值即可。
常见假解:枚举所有下标对只检查差为 1 但写成 O(n2) 无妨(n≤100),真正易错是误把「相邻下标」当成「相邻数值」,或只看相邻下标的值差。
现给定数组 numbers 记录了从 1 到 numbers.length 的乱序排列的整数,请找到整数值连续但相隔最远的两数之间的距离。
|numbers[i] - numbers[j]| == 1numbers[i] 与 numbers[j] 的距离,指下标差绝对值 |i - j|2 <= numbers.length <= 100
一个整数,表示所求最远的距离
输入:
[6, 4, 2, 5, 1, 3]
输出:
4
解释:
numbers[1] = 4, numbers[5] = 3; 连续整数 4、3 之间的距离(即下标差)为 4,最远。
其它距离都小于 4,例如 6 和 5 的距离为 3。
输入:
[2, 3, 6, 5, 7, 1, 4]
输出:
5
解释:
2 和 1 的距离为 5,3 和 4 的距离也为 5。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册