904. Fruit Into Baskets - Medium

前往題目

想法

• 找連續最多的區間，但可以容忍有一種不一樣的

思路

sliding window的一大重點: shrink

1. 右指針疊代整個陣列，左指針視情況移動
2. 每次疊代都把當前水果放入籃子
3. 如果invalid，shrink直到valid
4. 更新長度
5. 結束疊代回傳結果

Code

class Solution {
    public int totalFruit(int[] fruits) {
        // fruit type -> count in basket
        HashMap<Integer, Integer> count = new HashMap<>();

        int l = 0, total = 0, res = 0;

        for (int r = 0; r < fruits.length; ++r) {
            // Put it into the basket
            count.put(fruits[r], count.getOrDefault(fruits[r], 0) + 1);
            ++total;

            // Make the pick valid
            while (count.size() > 2) {
                int fruit = fruits[l]; // Get the leftmost fruit

                if (count.get(fruit) == 1) {
                    count.remove(fruit);
                } else {
                    count.put(fruit, count.getOrDefault(fruit, 0) - 1); // Take 1 out from the basket
                }
                --total;
                ++l;
            }

            // Once valid, update the result
            res = Math.max(res, total);
        }

        return res;
    }
}