สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และค่า k อันดับแรก เราจะลบรายการย่อยของขนาด k แล้วหาค่าต่ำสุดของ (จำนวนสูงสุด - ค่าต่ำสุดของจำนวน)
ดังนั้น หากอินพุตเป็น nums =[2, 3, 10, 9, 8, 4] k =3 ผลลัพธ์จะเป็น 2 หากเราลบ [10, 9, 8] เราจะได้ [2, 3, 4] และ 4 - 2 =2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
N :=ขนาดของ nums
-
คัดลอก nums ลงใน lmin และ lmax
-
คัดลอก nums ลงใน rmin และ rmax ด้วย
-
สำหรับผมอยู่ในช่วง 1 ถึง N - 1 ทำ
-
lmin[i] :=ขั้นต่ำของ lmin[i] และ lmin[i - 1]
-
lmax[i] :=สูงสุดของ lmax[i] และ lmax[i - 1]
-
-
สำหรับฉันในช่วง N - 2 ถึง 0 ลดลง 1 ทำ
-
rmin[i] :=ขั้นต่ำของ rmin[i] และ rmin[i + 1]
-
rmax[i] :=สูงสุดของ rmax[i] และ rmax[i + 1]
-
-
ans :=ขั้นต่ำของ (rmax[k] - rmin[k]), (lmax[complement of k] - lmin[complement of k])
-
สำหรับฉันในช่วง 0 ถึง N - k - 2 ทำ
-
cand :=(สูงสุดของ lmax[i] และ rmax[i + k + 1]) - (ค่าต่ำสุดของ lmin[i] และ rmin[i + k + 1])
-
ans :=ขั้นต่ำของ ans และ cand
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(nums, k): N = len(nums) lmin, lmax = nums[:], nums[:] rmin, rmax = nums[:], nums[:] for i in range(1, N): lmin[i] = min(lmin[i], lmin[i - 1]) lmax[i] = max(lmax[i], lmax[i - 1]) for i in range(N - 2, -1, -1): rmin[i] = min(rmin[i], rmin[i + 1]) rmax[i] = max(rmax[i], rmax[i + 1]) ans = min(rmax[k] - rmin[k], lmax[~k] - lmin[~k]) for i in range(N - k - 1): cand = max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1]) ans = min(ans, cand) return ans nums = [2, 3, 10, 9, 8, 4] k = 3 print(solve(nums, k))
อินพุต
[2, 3, 10, 9, 8, 4], 3
ผลลัพธ์
2
