สมมติว่าเรามีรายการของตัวเลขที่เรียกว่า nums เราต้องหาความแตกต่างสูงสุดที่มีอยู่ระหว่างตัวเลขใดๆ กับจำนวนที่น้อยกว่าถัดไป เป้าหมายของเราคือการแก้ปัญหานี้ในเวลาเชิงเส้น
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[14, 2, 6, 35, 12] ผลลัพธ์จะเป็น 21 เนื่องจาก 35 และ 14 มีความแตกต่างมากที่สุดคือ 21
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
max_val :=สูงสุดของ nums, min_val :=ขั้นต่ำของ nums
-
ถ้า max_val เหมือนกับ min_val แล้ว
-
คืนค่า 0
-
-
เดลต้า :=(max_val − min_val) / (ขนาดของ nums − 1)
-
min_map :=แผนที่ว่าง (ถ้าค่าบางค่าไม่มีให้คืนค่าเป็น inf)
-
max_map :=แผนที่ว่าง (หากบางค่าไม่มีค่าส่งคืนเป็น −inf)
-
res :=0, idx :=0
-
สำหรับแต่ละ num เป็น num ทำ
-
idx :=พื้นของ ((num − min_val) / delta)
-
max_map[idx] :=สูงสุดของ max_map[idx] และ num
-
min_map[idx] :=ขั้นต่ำของ min_map[idx] และ num
-
-
ก่อนหน้า :=min_val
-
สำหรับฉันในช่วง 0 ถึงขนาดของ nums − 1 ทำ
-
ถ้า min_map[i] ไม่เหมือนกับ inf แล้ว
-
res :=สูงสุดของ res และ (min_map[i] − ก่อนหน้า)
-
ก่อนหน้า :=max_map[i]
-
-
-
ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
from collections import defaultdict
import math
class Solution:
def solve(self, nums):
max_val = max(nums)
min_val = min(nums)
if max_val == min_val:
return 0
delta = (max_val − min_val) / (len(nums) − 1)
min_map = defaultdict(lambda: float("inf"))
max_map = defaultdict(lambda: float("−inf"))
res = 0
idx = 0
for num in nums:
idx = math.floor((num − min_val) / delta)
max_map[idx] = max(max_map[idx], num)
min_map[idx] = min(min_map[idx], num)
prev = min_val
for i in range(len(nums)):
if min_map[i] != float("inf"):
res = max(res, min_map[i] − prev)
prev = max_map[i]
return res
ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums)) อินพุต
[14, 2, 6, 35, 12]
ผลลัพธ์
21
