// MARK: - 42. Trapping Rain Water
// По ландшафту определите определите сколько блоков воды осталось после дождя в низинах на острове

// Находим маскимум
// Все что левее максимума будет стекать влево, аналогично справа от максимума
// для левой части будем запоминать максимум

func waterBlocks(arrayBlocks: [Int]) -> Int {
    var maxIndex = 0
    var max = arrayBlocks[maxIndex]
    for index in 0..<arrayBlocks.count {
        if arrayBlocks[index] > max {
            max = arrayBlocks[index]
            maxIndex = index
        }
    }
    var totalWater = 0
    var maxHeight = arrayBlocks[0]
    for index in 0...maxIndex {
        if arrayBlocks[index] > maxHeight {
            maxHeight = arrayBlocks[index]
        }
        totalWater += maxHeight - arrayBlocks[index]
    }
    maxHeight = arrayBlocks[arrayBlocks.count-1]
    for index in stride(from: arrayBlocks.count - 1, through: maxIndex, by: -1) {
        if arrayBlocks[index] > maxHeight {
            maxHeight = arrayBlocks[index]
        }
        totalWater += maxHeight - arrayBlocks[index]
    }
    return totalWater
}

let arrayBlocks = [3, 1, 4, 3, 5, 1, 1, 3, 1]
waterBlocks(arrayBlocks: arrayBlocks)