\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

Tìm \(max\), \(min\) của dãy \(a\)

Tạo ra mảng \(amx\) chứa các vị trí \(p\) mà \(a_p = max\)

Tạo ra mảng \(amn\) chứa các vị trí \(p\) mà \(a_p = min\)

Duyệt qua 2 mảng, tìm \(min{ |amx_i - amn_j| + 1 }\)

\(\color{orange}{\text{Hint 2 <Binary-Search>}}\)

Nhận xét rằng nếu ta nhận lần lượt các giá trị \(a[p]\) cho 2 mảng \(amn\) và \(amx\) thì nó đã được sắp xếp

Áp dụng điều này, duyệt mỗi \(x \in amx[]\) và tìm \(min{ |x - amn_i| }\)

Lưu ý xét cả 2 số \(amn_i \leq x\) và \(amn_{i + 1} \geq x\)

\(\color{orange}{\text{Hint 3 <Two-pointers>}}\)

Tương tự như trên, nhưng ta nhận thấy nếu 2 mảng \(amn\) và \(amx\) cùng sort theo độ ưu tiên như nhau (cùng tăng hoặc cùng giảm) thì ta có thể tăng dần vị trí con trỏ của một bên tới khi nó đạt giá trị phù hợp nhất và cập nhật kết quả