Cho một danh sách số nums, tìm hiệu số lớn nhất tồn tại giữa bất kỳ số nào và số nhỏ hơn ngay sau nó (theo thứ tự giá trị). Mục tiêu giải quyết trong thời gian tuyến tính.
Ví dụ, nums = [14, 2, 6, 35, 12], đầu ra là 21 (35 và 14 có hiệu số lớn nhất 21).
Giải pháp
Sử dụng thuật toán Pigeonhole Sort / Bucket Sort:
- Tìm max_val, min_val. Nếu bằng nhau trả về 0
- delta := (max_val - min_val) / (n - 1)
- Chia khoảng giá trị thành n - 1 bucket, mỗi bucket lưu min và max
- Đặt mỗi số vào bucket tương ứng
- Duyệt các bucket không rỗng, tính hiệu giữa min của bucket hiện tại và max của bucket trước
Ví dụ minh họa
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
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))
Đầu vào
[14, 2, 6, 35, 12]
Đầu ra
21