ในข้อนี้ กำหนดให้อาร์เรย์ $A$ ประกอบไปด้วยความสูงของตึก ณ เวลาใด ๆ โดย $A_i$ เมื่อ $0 \leq i \leq n - 1$ เป็นความสูงของตึกตำแหน่ง $i$

เมื่อมีการสร้างตึก ณ ตำแหน่ง $i$ โดยมีความสูง $h$ เราจะกำหนดให้ $A_i := h$ และค่า $d$ ของตึกนี้ จะเป็นไปได้ 2 กรณีได้แก่

1. ตึกนี้เป็นตึกที่สูงที่สุด ดังนั้นจะได้ว่า $d = n$
2. มีอย่างน้อยหนึ่งตึก $j$ ที่ $A_j > A_i$ ดังนั้นจะได้ว่า $d = (\min \limits_{0 \leq j \leq n - 1, A_j > A_i} |i - j|) - 1$

สำหรับกรณีที่ 2 หากเราไล่หาทีละ $j$ จะทำให้ใช้เวลา $\mathcal{O}(n)$ ต่อการสร้างตึก แต่สังเกตว่าตึก $i$ จะเป็นตึกที่สูงที่สุดในระยะ $k$ กิโลเมตร ก็ต่อเมื่อ $\max(\max\{A_{i - k}, A_{i - k + 1}, \dots, A_{i - 1}\}, \max\{A_{i + 1}, A_{i + 2}, \dots, A_{i + k}\}) \leq A_i$ และเมื่อตึก $i$ เป็นตึกที่สูงที่สุดในระยะ $k$ กิโลเมตรแล้ว ก็จะได้ว่าเป็นตึกที่สูงที่สุดในระยะ $0, 1, 2, \dots, k - 1$ กิโลเมตรเช่นกัน

ดังนั้น จากคุณสมบัติด้านบนนี้ เราจะสามารถ Binary Search เพื่อหา $k$ ที่มากที่สุดที่ตึก $i$ ยังคงเป็นตึกที่สูงที่สุดในระยะ $k$ กิโลเมตร โดยสำหรับการหาค่า $\max\{A_{i - k}, A_{i - k + 1}, \dots, A_{i - 1}\}$ และ $\max\{A_{i + 1}, A_{i + 2}, \dots, A_{i + k}\}$ สามารถหาได้ภายใน $\mathcal{O}(\log n)$ ด้วยการเก็บอาร์เรย์ $A$ ในรูปของ Segment Tree ที่รองรับการหาค่าที่มากที่สุดเป็นช่วงนั่นเอง

จากวิธีดังกล่าว ในการสร้างตึกแต่ละครั้ง เราจะสามารถหาค่า $d$ ได้ภายในเวลา $\mathcal{O}(\log^2 n)$ หรือ $\mathcal{O}(\log n)$ ขึ้นกับการ Implementation

Time Complexity: $\mathcal{O}(k \log^2 n)$ หรือ $\mathcal{O}(k \log n)$