904. 水果成篮

904. 水果成篮

滑动窗口。算法内容参考209.

我先自己写了个：

class Solution {
  public:
	int totalFruit(vector<int> &fruits)
	{
		int i = 0, j = 0, n = fruits.size(), res = 0;
        vector<int> basket(n,0);
        int basket_num = 0;
        for(j = 0; j < n; j++){
			if (basket[fruits[j]] == 0){
                basket_num++;
            }
			basket[fruits[j]]++;
			if (basket_num > 2){
				res = max(res, j - i);
				while (basket_num > 2) {
					basket[fruits[i]]--;
					if (basket[fruits[i]] == 0) {
						basket_num--;
					}
					i++;
				}
			}
		}
		res = max(res, j - i);
        return res;
	}
};

这个正确性和算法时间复杂度没问题，过了。

分析

这道题和209是同一个算法的对立两面。

209想要求满足条件下的最短窗口，904想要求满足条件下的最长窗口。

这里我们先把比较标准的904代码放出来,再把209的拿过来，把两个代码进行对比：

209：

class Solution {
  public:
	int minSubArrayLen(int target, vector<int> &nums)
	{
		int i = 0, j = 0, sum = 0, n = nums.size(), res = n + 1;
		for (j = 0; j < n; j++) {
			sum += nums[j];
			while (sum >= target) {
				res = min(res, j - i + 1);
				sum -= nums[i++];
			}
		}
		if (res == n + 1) {
			res = 0;
		}
		return res;
	}
};

904:

class Solution {
  public:
	int totalFruit(vector<int> &fruits)
	{
		int i = 0, j = 0, n = fruits.size(), res = 0;
        vector<int> basket(n,0);
        int basket_num = 0;
        for(j = 0; j < n; j++){
			if (basket[fruits[j]] == 0){
                basket_num++;
            }
			basket[fruits[j]]++;
            while (basket_num > 2) {
                basket[fruits[i]]--;
                if (basket[fruits[i]] == 0) {
                    basket_num--;
                }
                i++;
            }
			res = max(res, j - i + 1);
		}
        return res;
	}
};

请尤其关注for循环内步骤：

• 209

for (j = 0; j < n; j++) {
	// 将j往后延伸，并把新元素加入窗口
	sum += nums[j];
	
	// 检查是否合法，合法则开始清除i端元素出去
	while (sum >= target) {
		// 更新记录，在清除最后一个i端元素进入非法前一直在更新
		res = min(res, j - i + 1);
		// 将i往后收缩，并把旧元素清出窗口
		sum -= nums[i++];
	}
}

• 904

for(j = 0; j < n; j++){
	// 将j往后延伸，并把新元素加入窗口
	if (basket[fruits[j]] == 0){
		basket_num++;
	}
	basket[fruits[j]]++;
	
	// 检查是否非法，非法则开始清除i端元素出去
	while (basket_num > 2) {
		// 将i往后收缩，并把旧元素清出窗口
		basket[fruits[i]]--;
		if (basket[fruits[i]] == 0) {
			basket_num--;
		}
		i++;
	}
	// 更新记录，只要合法就更新
	res = max(res, j - i + 1);
}

所以说，对209来说，for内，while外的部分是非法的，while的条件是合法；对904来说，for内，while外的部分才是合法的，while的条件是非法。这个区别源于他们的目标不同：209想要求合法下的最短窗口，904想要求合法下的最长窗口。

---

现在看看904如何操作元素，让元素“进入窗口”和“退出窗口”。

对209来说，他只是求个和，进来加一下，出去减一下就好了。

对904来说，他有2个篮子，每个果树一个果实，篮子里有多少也不知道。我们需要一个列表去维护身上每种果实有多少个。然后也监视现在有多少种水果，不能超过2种。

变量定义：

vector<int> basket(n,0);
int basket_num = 0;

basket这个vector用于存储种类号为i的水果有多少。初始全是0；basket_num用于记录有几个篮子有水果，也就是有几种水果的数量大于0.

这是进入窗口的代码：

if (basket[fruits[j]] == 0){
	basket_num++;
}
basket[fruits[j]]++;

basket[fruits[j]]代表即将进入的这种果子目前拥有的数量。如果是0,说明是新种类，需要一个新篮子，让basket_num加1.然后再让这个果子的数量+1.

这是退出窗口的代码：

basket[fruits[i]]--;
if (basket[fruits[i]] == 0) {
	basket_num--;
}

先让果子的数量-1.如果减了以后果子数量为0了，说明这类水果已经没了，这个篮子空出来了，占用的篮子少了一个。那就让basket_num减1。

这个两个过程是轴对称的。

---

904更新结果的位置在整个for循环的最后位置。这个位置代表着当前的状态一定是合法的。只两种情况：1.刚刚j延伸了一格，且合法了，直接跳过while到这里；2.延伸以后非法了，在while里面i收缩了一通，缩到合法了。在这里面1.才是我们需要关注的可能最长值。但是2放进来也没关系，因为一定要小一点，不会对max产生影响。

完整代码

class Solution {
  public:
	int totalFruit(vector<int> &fruits)
	{
		int i = 0, j = 0, n = fruits.size(), res = 0;
        vector<int> basket(n,0);
        int basket_num = 0;
        for(j = 0; j < n; j++){
			if (basket[fruits[j]] == 0){
                basket_num++;
            }
			basket[fruits[j]]++;
            while (basket_num > 2) {
                basket[fruits[i]]--;
                if (basket[fruits[i]] == 0) {
                    basket_num--;
                }
                i++;
            }
			res = max(res, j - i + 1);
		}
        return res;
	}
};