package daily.mid

fun main() {
    // 904. 水果成篮
    // https://leetcode.cn/problems/fruit-into-baskets/
    println(totalFruit(intArrayOf(1,2,3,2,2)))
}

fun totalFruit(fruits: IntArray): Int {
    // 其实就是找一个只包含两个元素的最长子序列
    // 用一个 hashMap 存储出现的元素，以及这个元素出现的次数
    // 且要保证 hashMap 中只能有2个键值对
    // 用双指针 left、right 执行第一个元素，用 right 遍历数组，把遍历到的元素，加入到 hashMap 中，
    // 如果加入 hashMap 之后，键值对数量大于 2，要把 left 指针右移，并把 left 指针指向的元素的出现次数-1，如果次数减少到0，要把这个元素从 map 中移除
    var left = 0
    var right = 0
    val map = HashMap<Int, Int>()
    var maxRange = 0
    while (right < fruits.size) {
        map[fruits[right]] = map.getOrDefault(fruits[right], 0) + 1
        while (map.size > 2) {
            // 键值对数量超过2，left 指针右移
            map[fruits[left]] = map.getOrDefault(fruits[left], 0) - 1
            if (map[fruits[left]]!! <= 0) {
                map.remove(fruits[left])
            }
            left++
        }
        val tmpRange = right - left + 1
        if (tmpRange > maxRange) {
            maxRange = tmpRange
        }
        right++
    }
    return maxRange
}