Bài 11.4. Quản Lý Độ Ẩm - [Độ khó: Khó]

Mô tả bài tập: Trong một dự án nông nghiệp thông minh, bạn được giao nhiệm vụ phân tích dữ liệu độ ẩm đất thu thập từ các cảm biến. Dữ liệu được ghi lại hàng giờ dưới dạng một mảng các số nguyên. Các nhà khoa học muốn tìm một khoảng thời gian liên tục có độ dài đúng bằng K giờ mà trong khoảng đó, sự biến động độ ẩm là nhỏ nhất. Sự biến động của một khoảng được định nghĩa là hiệu số giữa giá trị độ ẩm lớn nhất và giá trị độ ẩm nhỏ nhất trong khoảng đó. Nhiệm vụ của bạn là tìm giá trị biến động nhỏ nhất này.

INPUT FORMAT Dòng đầu tiên chứa hai số nguyên N và K (1 <= K <= N <= 10^5). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (0 <= a_i <= 10^9) là các giá trị độ ẩm được ghi lại.

OUTPUT FORMAT In ra một số nguyên duy nhất là giá trị biến động nhỏ nhất tìm được.

Ví dụ: Input:

5 3
10 12 15 18 20

Output:

5

Giải thích:

• Mảng độ ẩm: [10, 12, 15, 18, 20], K = 3.
• Ta xét tất cả các "cửa sổ trượt" có độ dài K=3:
  • Cửa sổ 1 (từ chỉ số 0 đến 2): [10, 12, 15]
    • Giá trị nhỏ nhất: 10
    • Giá trị lớn nhất: 15
    • Biến động: 15 - 10 = 5
  • Cửa sổ 2 (từ chỉ số 1 đến 3): [12, 15, 18]
    • Giá trị nhỏ nhất: 12
    • Giá trị lớn nhất: 18
    • Biến động: 18 - 12 = 6
  • Cửa sổ 3 (từ chỉ số 2 đến 4): [15, 18, 20]
    • Giá trị nhỏ nhất: 15
    • Giá trị lớn nhất: 20
    • Biến động: 20 - 15 = 5
• Giá trị biến động nhỏ nhất trong số các cửa sổ này là 5.