สมมติว่าเรามีอาร์เรย์ nums ramp คือคู่ (i, j) ที่ i < j และ nums[i] <= nums[j] ความกว้างของ ramp คือ (j-i) เราต้องหาความกว้างสูงสุดของ ramp ใน nums ถ้าไม่พบ return 0
เช่น ถ้าอินพุตคือ nums = [6,0,8,2,1,5] ผลลัพธ์จะเป็น 4 เพราะ ramp ความกว้างสูงสุดอยู่ที่ (i, j) = (1, 5) และ nums[1] = 0 และ nums[5] = 5
วิธีแก้ปัญหา
- B := แมปใหม่
- สำหรับ i ในช่วง 0 ถึงขนาดของ nums:
- x := nums[i]
- ถ้า x อยู่ใน B: เพิ่ม i ลงท้าย B[x]
- มิฉะนั้น: B[x] := [i]
- mini := รายการเริ่มต้นเก็บ inf หนึ่งค่า
- maxi := รายการเริ่มต้นเก็บ -inf หนึ่งค่า
- สำหรับแต่ละ x ในรายการคีย์ของ B ที่เรียงแล้ว:
- เพิ่ม min(ค่าสุดท้ายของ mini, min ของ B[x]) ลงท้าย mini
- สำหรับแต่ละ x ในรายการคีย์ของ B ที่เรียงย้อนกลับ:
- เพิ่ม max(ค่าสุดท้ายของ maxi, max ของ B[x]) ลงท้าย maxi
- maxi := ย้อนกลับ maxi แล้ว取สไลซ์จากต้นถึงตัวก่อนหน้าสุดท้าย
- mini := สไลซ์ของ mini[จากดัชนี 1 ถึงสุด]
- p := 0, res := -inf
- while p < ขนาดของ mini:
- res := max(res, maxi[p] - mini[p])
- p := p + 1
- return res
ตัวอย่าง
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))
อินพุต
[6,0,8,2,1,5]
เอาต์พุต
4
