https://leetcode.com/problems/fruit-into-baskets/
https://leetcode.com/problems/fruit-into-baskets/discuss/170745/Problem%3A-Longest-Subarray-With-2-Elements
https://leetcode.com/problems/fruit-into-baskets/discuss/171954/Java-Very-simple-solution-few-lines-Time-O(n)-Space-O(1)
Approach 1: Scan Through Blocks
In a row of trees, the
i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:
- Add one piece of fruit from this tree to your baskets. If you cannot, stop.
- Move to the next tree to the right of the current tree. If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?
Example 1:
Input: [1,2,1] Output: 3 Explanation: We can collect [1,2,1].
Example 2:
Input: [0,1,2,2] Output: 3 Explanation: We can collect [1,2,2]. If we started at the first tree, we would only collect [0, 1].
Example 3:
Input: [1,2,3,2,2] Output: 4 Explanation: We can collect [2,3,2,2]. If we started at the first tree, we would only collect [1, 2].
Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4] Output: 5 Explanation: We can collect [1,2,1,1,2]. If we started at the first tree or the eighth tree, we would only collect 4 fruits.
https://blog.csdn.net/fuxuemingzhu/article/details/82906745
现在LeetCode就喜欢出一个情景题，让人花了很长时间理解题意，并且抽象出来。这个题如果抽象成模型的话就是，求一个数组的最长连续子数组，要求这个子数组中最多只存在两个不同的元素。
如果做了上面的抽象，那么我们就很容易想到使用双指针，计算双指针区间内的所有元素的个数，这个个数就是我们要求的能摘取的果子个数。同时在移动的过程中要保证，双指针区间内的元素种类最多为2.之前做题的时候有使用Counter直接数一个区间内所有的个数，这样会超时的。所以使用了字典进行存储，每次只更新最右边和最左边的元素的个数即可。
This is essentially the same question as: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ . Just imagine each number as a character
https://leetcode.com/problems/fruit-into-baskets/discuss/170740/Sliding-Window
现在LeetCode就喜欢出一个情景题，让人花了很长时间理解题意，并且抽象出来。这个题如果抽象成模型的话就是，求一个数组的最长连续子数组，要求这个子数组中最多只存在两个不同的元素。
如果做了上面的抽象，那么我们就很容易想到使用双指针，计算双指针区间内的所有元素的个数，这个个数就是我们要求的能摘取的果子个数。同时在移动的过程中要保证，双指针区间内的元素种类最多为2.之前做题的时候有使用Counter直接数一个区间内所有的个数，这样会超时的。所以使用了字典进行存储，每次只更新最右边和最左边的元素的个数即可。
This is essentially the same question as: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ . Just imagine each number as a character
https://leetcode.com/problems/fruit-into-baskets/discuss/170740/Sliding-Window
"Start from any index, we can collect at most two types of fruits. What is the maximum amount"
public int totalFruit(int[] tree) {
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
int res = 0, i = 0;
for (int j = 0; j < tree.length; ++j) {
count.put(tree[j], count.getOrDefault(tree[j], 0) + 1);
while (count.size() > 2) {
count.put(tree[i], count.get(tree[i]) - 1);
if (count.get(tree[i]) == 0) count.remove(tree[i]);
i++;
}
res = Math.max(res, j - i + 1);
}
return res;
}
- 这道题实际上是找到一段最长的距离，使得这段距离内包含的元素只有两种，显然双指针解决，使用一个字典存储已经有的元素及对应的数量。
- 对tree[j]分析时，若向字典中加入tree[j]使得字典中元素数量大于2，便开始从左开始删元素，直至字典元素只剩1种，然后将tree[j]加入
- 每进行2操作之前需要先比较一次长度，取最大长度作为结果
As in Approach 1, we want the longest subarray with at most two different "types" (values of
tree[i]). Call these subarrays valid.
Say we consider all valid subarrays that end at index
j. There must be one with the smallest possible starting index i: lets say opt(j) = i.
Now the key idea is that
opt(j) is a monotone increasing function. This is because any subarray of a valid subarray is valid.
Algorithm
Let's perform a sliding window, keeping the loop invariant that
i will be the smallest index for which [i, j]is a valid subarray.
We'll maintain
count, the count of all the elements in the subarray. This allows us to quickly query whether there are 3 types in the subarray or not.
public int totalFruit(int[] tree) {
int ans = 0, i = 0;
Counter count = new Counter();
for (int j = 0; j < tree.length; ++j) {
count.add(tree[j], 1);
while (count.size() >= 3) {
count.add(tree[i], -1);
if (count.get(tree[i]) == 0)
count.remove(tree[i]);
i++;
}
ans = Math.max(ans, j - i + 1);
}
return ans;
}
}
class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}
public void add(int k, int v) {
put(k, get(k) + v);
}
public int totalFruit(int[] tree) {
int start = 0;
int n = tree.length;
int maxLength = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int end = 0; end < n; end++) {
map.put(tree[end], end);
if (map.size() > 2) {
int minIndex = Collections.min(map.values());
map.remove(tree[minIndex]);
start = minIndex + 1;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
Loop all fruit
Note that
so it's something like "....aaabbbc..."
c in tree,Note that
a and b are the last two different types of fruit that we met,c is the current fruit type,so it's something like "....aaabbbc..."
Case 1
fruit
and it's same as the last type of fruit
c == b:fruit
c already in the basket,and it's same as the last type of fruit
cur += 1count_b += 1
Case 2
fruit
but it's not same as the last type of fruit
c == a:fruit
c already in the basket,but it's not same as the last type of fruit
cur += 1count_b = 1a = b, b = c
Case 3
fruit
c != b && c!= a:fruit
c not in the basket,cur = count_b + 1count_b = 1a = b, b = c
Of course, in each turn we need to update
res = max(res, cur) public int totalFruit(int[] tree) {
int res = 0, cur = 0, count_b = 0, a = 0, b = 0;
for (int c : tree) {
cur = c == a || c == b ? cur + 1 : count_b + 1;
count_b = c == b ? count_b + 1 : 1;
if (b != c) {a = b; b = c;}
res = Math.max(res, cur);
}
return res;
}https://leetcode.com/problems/fruit-into-baskets/discuss/171954/Java-Very-simple-solution-few-lines-Time-O(n)-Space-O(1)
public int totalFruit(int[] tree) {
int max = 0, count = 0;
for (int i = 0, first = 0, second = -1; i < tree.length; i++) {
count++;
if (tree[i] == tree[first]) {
first = i;
} else if (second == -1 || tree[i] == tree[second]) {
second = i;
} else {
max = Math.max(count - 1, max);
count = Math.abs(first - second) + 1;
first = i - 1;
second = i;
}
}
return Math.max(count, max);
}Approach 1: Scan Through Blocks
Intuition
Equivalently, we want the longest subarray with at most two "types" (values of
tree[i]).
Instead of considering each element individually, we can consider blocks of adjacent elements of the same type.
For example, instead of
tree = [1, 1, 1, 1, 2, 2, 3, 3, 3], we can say this is blocks = [(1, weight = 4), (2, weight = 2), (3, weight = 3)].
Now say we brute forced, scanning from left to right. We'll have something like
blocks = [1, _2_, 1, 2, 1, 2, _1_, 3, ...] (with various weights).
The key insight is that when we encounter a
3, we do not need to start from the second element 2(marked _2_ for convenience); we can start from the first element (_1_) before the 3. This is because if we started two or more elements before, the sequence must have types 1 and 2, and that sequence is going to end at the 3, and thus be shorter than anything we've already considered.
Since every starting point (that is the left-most index of a block) was considered, this solution is correct.
Algorithm
As the notation and strategy around implementing this differs between Python and Java, please see the inline comments for more details.
- Time Complexity: , where is the length of
tree. - Space Complexity: .
public int totalFruit(int[] tree) {
// We'll make a list of indexes for which a block starts.
List<Integer> blockLefts = new ArrayList();
// Add the left boundary of each block
for (int i = 0; i < tree.length; ++i)
if (i == 0 || tree[i - 1] != tree[i])
blockLefts.add(i);
// Add tree.length as a sentinel for convenience
blockLefts.add(tree.length);
int ans = 0, i = 0;
search: while (true) {
// We'll start our scan at block[i].
// types : the different values of tree[i] seen
// weight : the total number of trees represented
// by blocks under consideration
Set<Integer> types = new HashSet();
int weight = 0;
// For each block from the i-th and going forward,
for (int j = i; j < blockLefts.size() - 1; ++j) {
// Add each block to consideration
types.add(tree[blockLefts.get(j)]);
weight += blockLefts.get(j + 1) - blockLefts.get(j);
// If we have 3+ types, this is an illegal subarray
if (types.size() >= 3) {
i = j - 1;
continue search;
}
// If it is a legal subarray, record the answer
ans = Math.max(ans, weight);
}
break;
}
return ans;
}
