[数据结构与算法]LeetCode904.水果成篮 -- 滑动窗口

?1.问题描述

2.思路:
? ? 类似于滑动窗口的多指针解法
? ? 我们需要在遍历fruits,索引为i时,不断更新以下三个指针:
? ? 当下的两个篮子第一个篮子起始索引first,
? ? 当下的两个篮子第二个篮子起始索引second,
? ? 未来的两个篮子第一个篮子的起始索引temp,
? ? 计算两个篮子中 i - first + 1的最大值即可求出水果最大长度len
如何计算first:
? ? 遍历fruits记录第一个出现的篮子的索引,
? ? 当遍历到出现第三个篮子时(fruits[i] != fruits[first] && fruits[i] != fruits[second])将其更新为temp,
? ? first = temp,保证计算len时同时出现的只有两个篮子
如何计算second:
? ? 遍历fruits记录第二个出现的篮子的索引,
? ? 当遍历到出现第三个篮子时(fruits[i] != fruits[first] && fruits[i] != fruits[second])将其更新为i,
? ? second = i,保证计算len时同时出现的只有两个篮子
如何计算temp:
? ? 以010123为例，
? ? 遍历完索引为3（值为1）时(只有两个篮子)，first = 0，second = 1，temp = 3。
? ? 遍历完索引为4（值为2）时(出现三个篮子)，first = 3，second = 4，temp = 4。
? ? 以010023为例，
? ? 遍历完索引为3（值为0）时(只有两个篮子)，first = 0，second = 1，temp = 2。
? ? 遍历完索引为4（值为2）时(出现三个篮子)，first = 2，second = 4，temp = 4。
? ? 有如下规律:
? ? 当下两个篮子中最后出现的篮子从后往前连续相等最长的起始索引,即为未来的两个篮子中第一个篮子的起始索引
? ? 0101最后出现的篮子是1索引是3,和1从后往前连续相等最长的索引还是3
? ? 0100最后出现的篮子时0索引是3,和0从后往前连续相等最长的索引是2

3.代码

class Solution {
    public int totalFruit(int[] fruits) {
        if (fruits.length == 0) {
            return 0;
        }
        int len = 0,first = 0,second = 0,temp = 0;
        for (int i = 0; i < fruits.length; i++) {
            //判断是否出现第三个篮子
            if (fruits[i] != fruits[first] && fruits[i] != fruits[second]){
                //只有初始化时,第一个篮子和第二个篮子都为0时才相等
                //相等时出现的是第二个篮子,故不用更新first,只需要更新second
                //不相等时出现的是第三个篮子,故first,second都需要更新
                if(first != second) {
                    first = temp;
                }
                second = i;
            }
            //更新len最大值
            len = Math.max(len,i - first + 1);
            //计算temp
            if(fruits[temp] != fruits[i]){
                temp = i;
            }
        }
        return len;
    }
}

4.执行结果

?