Cho mảng nums, ramp là cặp (i, j) với i < j và nums[i] <= nums[j]. Độ rộng = j-i. Tìm độ rộng ramp lớn nhất. Nếu không có trả về 0.
Ví dụ: nums = [6,0,8,2,1,5], đầu ra = 4 (ramp tại (1,5): nums[1]=0, nums[5]=5).
Giải pháp
Nhóm chỉ số theo giá trị, tính min prefix và max suffix:
- B := map giá trị -> danh sách chỉ số
- mini := [inf], maxi := [-inf]
- Duyệt key tăng dần: mini.append(min(mini[-1], min(B[x])))
- Duyệt key giảm dần: maxi.append(max(maxi[-1], max(B[x])))
- maxi := reverse(maxi)[:-1], mini := mini[1:]
- Tìm max(maxi[p] - mini[p])
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(nums):
B = {}
for i in range(len(nums)):
x = nums[i]
if x in B:
B[x].append(i)
else:
B[x] = [i]
mini = [float('inf')]
maxi = [float('-inf')]
for x in sorted(B.keys()):
mini.append(min(mini[-1], min(B[x])))
for x in sorted(B.keys(), reverse=True):
maxi.append(max(maxi[-1], max(B[x])))
maxi = maxi[::-1][:-1]
mini = mini[1:]
p = 0
res = float('-inf')
while p < len(mini):
res = max(res, maxi[p] - mini[p])
p += 1
return res
nums = [6,0,8,2,1,5]
print(solve(nums))
Đầu vào
[6,0,8,2,1,5]
Đầu ra
4