🌕 904. 水果成篮

难度: 🌕

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    int[] buchets = new int[] {-1, -1};
    public int totalFruit(int[] fruits) {
        // 思路：
        // 滑动窗口
        // 只能存放 2 个不同的值，求区间最大长度
        int len = fruits.length;
        int res = 0;
        int left = 0;
        int right = 0;
        while(right < len) {
            // 找以 left 为左边界，最大的右边界
            while(right < len && isValid(fruits[right])) {
                right ++;
            }
            // [right] 不合适，不能选择 right 这个水果
            // System.out.println("left : " + left + "right : " + right);
            res = Math.max(res, right - left);
            if(right == len) {
                break; // 右边界已经遍历完，说明不论是否移动左边界，都没有比这个结果更大的了
            }
            // 移除一种篮子水果，移除标准是这种水果不是当前右边界选中的水果
            int leftVal = fruits[right - 1];
            buchets = new int[] {leftVal, -1}; // 清空篮子，只存放右边界水果
            int n = right - 1;
            while(fruits[n] == leftVal) {
                n --;
            }
            // [n] != leftVal
            left = n + 1;
            // System.out.println("   -------    left : " + left + "right : " + right);
        }
        return res;
    }

    private boolean isValid(int curVal) {
        if(buchets[0] == -1 && buchets[1] == -1) {
            buchets[0] = curVal;
            return true;
        }
        if(buchets[0] == curVal || buchets[1] == curVal) {
            return true;
        }
        // 没有满足条件的篮子
        if(buchets[0] == -1) {
            buchets[0] = curVal;
            return true;
        }
        if(buchets[1] == -1) {
            buchets[1] = curVal;
            return true;
        }
        return false;
    }
}

---

输出