Trapping rain water

n ta manfiy bo'lmagan butun sonlar (har biri kengligi 1 bo'lgan ustun balandligini bildiradi) height massivi orqali berilgan. Yomg'ir yoqqanidan so'ng ushbu hududda qancha miqdorda suv to'planib qolishini hisoblang.

func solve(height []int) int {
    // ...
}

Misollar

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Input: height = [4,2,0,3,2,5]
Output: 9

Input: height = [1,1]
Output: 0

Maslahatlar

1. Har bir ustun ustidagi suv miqdori "chapdagi eng baland ustun" va "o'ngdagi eng baland ustun"ning kichigi bilan cheklanadi — buni oldindan hisoblab qo'yish o'rniga ikkita ko'rsatkich (chapdan va o'ngdan) bilan bitta o'tishda hisoblash mumkin.
2. left va right ko'rsatkichlarini massiv chetlaridan boshlang, leftMax va rightMax ni kuzatib boring. Har qadamda height[left] va height[right] ni solishtirib, qaysi tomon kichik bo'lsa o'sha tomonni ishlating: agar height[left] < height[right] bo'lsa, height[left] ni leftMax bilan solishtirib (agar undan katta bo'lsa leftMax ni yangilang, aks holda leftMax-height[left] miqdorda suv qo'shing) left++ qiling; aks holda xuddi shunday right tomon uchun bajaring. Bu ishlaydi, chunki kichikroq tomonning suv sathi albatta ikkala tomon maksimumining kichigi bilan belgilanadi.