กำหนดให้ $A$ เป็นอาร์เรย์ที่ประกอบไปด้วยความสูงของสันเขา และ $A_i$ แทนความสูงของสันเขาที่ $i$

สังเกตว่าในการดึงสันเขา ขนาดของช่วงที่มีความสูงเท่ากัน จะเปลี่ยนแปลงก็ต่อเมื่อ $h \in A$ ดังนั้นในการหาคำตอบ เราจึงจำเป็นต้อง พิจารณา $h$ ที่แตกต่างกันเพียง $n$ ค่าเท่านั้น

เราจะพิจารณา $h = A_1, A_2, \dots, A_n$ โดยสำหรับแต่ละค่า $h = A_i$ เราจะหาขนาดของช่วงที่ติดกัน เมื่อช่วงดังกล่าวต้องมีสันเขาที่ $i$ ประกอบอยู่ด้วย

สังเกตว่าสันเขาภายในช่วงดังกล่าว ความสูงเดิมจะต้องมีค่าไม่น้อยกว่า $A_i$ และสันเขาที่ถัดจากช่วงนี้ไปทางซ้ายและขวา จะมีความสูงน้อยกว่า $A_i$ มิฉะนั้น จะต้องรวมสันเขานี้เข้าไปในช่วงด้วย ดังนั้น กำหนดให้ช่วง $[l, r]$ เมื่อ $l \leq i \leq r$ เป็นช่วงของสันเขา $A_i$ เราจะได้ว่า $\min\{A_l, A_{l + 1}, \dots, A_r\} \geq A_i$

หากเราไล่ $l, r$ ทีละค่า จะใช้เวลา $\mathcal{O}(n)$ ต่อการหาขนาดช่วงหนึ่งครั้ง แต่เราสามารถลดเวลาการทำงานลง ด้วยคุณสมบัติที่ว่า หาก $\min\{A_x, A_{x + 1}, \dots, A_i\} \geq A_i$ ก็จะได้ว่า $\min\{A_{x'}, A_{x' + 1}, \dots, A_i\} \geq A_i$ เมื่อ $x' > x$ เช่นกัน และหาก $\min\{A_i, A_{i + 1}, \dots, A_y\} \geq A_i$ ก็จะได้ว่า $\min\{A_i, A_{i + 1}, \dots, A_{y'}\} \geq A_i$ เมื่อ $y' < y$ เช่นกัน

จากคุณสมบัติดังกล่าว เราจึงสามารถ Binary Search ค่า $x$ และ $y$ ที่น้อยที่สุดและมากที่สุดตามลำดับ จะทำให้ได้ค่า $l$ และ $r$ จึงสรุปได้ว่าขนาดช่วงที่ประกอบไปด้วยสันเขา $i$ จะมีค่าเป็น $r - l$ นั่นเอง โดยสำหรับการหา $\min\{A_x, A_{x + 1}, \dots, A_i\}$ และ $\min\{A_i, A_{i + 1}, \dots, A_y\}$ เราสามารถใช้ Segment Tree ที่รองรับการหาค่าที่น้อยที่สุดในช่วง ทำให้การคิดขนาดช่วงแต่ละสันเขา ใช้เวลาเพียง $\mathcal{O}(\log n)$ หรือ $\mathcal{O}(\log^2 n)$ ขึ้นกับ Implementation

เมื่อทราบขนาดช่วงของแต่ละสันเขาเป็นที่เรียบร้อยแล้ว สำหรับปัญหาย่อยที่ 1, 2 และ 3 เราจะตอบความสูงของสันเขาที่มากที่สุดที่ขนาดช่วงมีค่าเท่ากับ $w$ หรือ $-1$ หากไม่มีสันเขาดังกล่าว

สำหรับปัญหาย่อยที่ 4 เราจะเก็บคำตอบในอาร์เรย์ $W$ เมื่อ $W_i$ เป็นความสูงของสันเขาที่มากที่สุดที่ขนาดช่วงมีค่าเท่ากับ $i$ หรือ $-1$ หากไม่มีสันเขาดังกล่าว ขณะที่คิดขนาดช่วงของสันเขาที่ $i$ สมมติให้ขนาดที่ได้เป็น $k$ เราก็จะกำหนดให้ $W_k := \max(W_k, A_i)$ นั่นเอง

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