rainWater

[Problem H – Sasuke CodeWar #28]

Trên một đoạn đường bị hư hỏng, có n điểm, độ cao ở mỗi điểm i của đường là a[i], khi trời mưa xuống thì những chỗ thấp hơn sẽ bị nước mưa lấp vào.

Lưu ý là riêng điểm 0 và điểm n-1 là hai lề đường nên không thể bị nước lấp vào.

Ví dụ như a = [10,5,14,8,10,13], thì sau khi trời mưa thì hình ảnh đoạn đường sẽ như sau.

Theo hình thì a[2]=5 đã bị nước lấp vào và có độ cao là 10, a[3], a[4] cũng bị nước lấp vào và có độ của là 13.

Hãy giúp Hải đưa ra độ cao của mỗi điểm trên đoạn đường khi đã bị nước mưa lấp vào.

Ví dụ:

• Với a = [10,5,14,8,10,13], thì rainWater = [10,10,14,13,13,13].
• Với a = [2,1,3], thì rainWater  = [2,2,3].

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] Array: Integer: 
  2 ≤ a.size() ≤ 105
1 ≤ a[i] ≤ 103
  

• [Đầu ra] Arrays: Integer
  Độ cao của tất cả các điểm trên đoạn đường.