LeetCode —— 滑动窗口-JZTXT

904. 水果成篮

用一个 Map 记录当前窗口的情况： key - 水果种类数 value - 这个水果种类在当前滑动窗口里出现的次数

维持一个 left 指针到 right 指针的滑动窗口

每次 right 右移一位，将新加入窗口的 fruits[right] 这个种类放到 map 里，并将该种类计数 +1

如果当前窗口水果种类数，即 map 的 size 大于规定的 2

那么需要左指针右移，维持窗口内种类的数量不大于 2

思考下 [1,0,1,4,]1,4,1,2,3 这种情况
在 [1,0,1,4,] 这个窗口，凭人的判断应该将左指针移到 1 这里，窗口变成 [1,4]
但是怎么用代码来实现这个逻辑呢？
我刚开始只用了 Set ，没有用 Map。想窗口最左边的元素是 1，那 left 移动到第一个不等于 1 的地方就行了，显然这种情况不适用

后来又想从窗口最右边往左找第一个不等于 1 的地方，对于这种情况也是不适用的

后面看了题解，正确的做法应该是

left 每右移一格，map 里这个种类窗口计数 -1

并且每次 -1 后判断，当前 left 的种类窗口计数是否减到了0

减到0，说明窗口没有这个数字了，remove 掉

对于上面的例子，窗口 [1,0,1,4]

leftIndex = 0 Map {1:2, 0:1, 4:1}

leftIndex = 1 Map {1:1, 0:1, 4:1}

leftIndex = 2 Map {1:1, 0:0, 4:1} --> Map {1:1, 4:1}

窗口里只剩两个种类了，可以退出循环了，最后窗口为 [1,4,]

class Solution {
    public int totalFruit(int[] fruits) {
        int left=0;
        int right=0;
        int maxRes = Integer.MIN_VALUE;
        Map<Integer, Integer> curWinKind2CntMap = new HashMap();
        while (right < fruits.length) {
            // 放入窗口右边的水果，并将计数 + 1
            // 注意 getOrDefault
            curWinKind2CntMap.put(fruits[right], curWinKind2CntMap.getOrDefault(fruits[right], 0) + 1);
            // 当窗口内种类数 > 2
            if (curWinKind2CntMap.size() > 2) {
                // left 左移，fruits[left] 种类数 -1
                curWinKind2CntMap.put(fruits[left], curWinKind2CntMap.get(fruits[left]) - 1);
                // 如果减到0，说明没有了，移除掉
                if (curWinKind2CntMap.get(fruits[left]) == 0) {
                    curWinKind2CntMap.remove(fruits[left]);
                }
                left++;
            }
            // 窗口大小
            int winLen = right - left + 1;
            // 与最大值比较
            if (winLen > maxRes) {
                maxRes = winLen;
            }
            right++;
        }
        return maxRes;
    }
}