904. fruit baskets

Title Description

You are visiting a farm , The farm planted a row of fruit trees from left to right . These trees use an array of integers fruits Express , among fruits[i] It's No i The fruit on the tree species .

You want to collect as much fruit as possible . However , The owner of the farm set some strict rules , You must pick the fruit as required ：

1, You only have   Two   Basket , And each basket can only hold   Single type   The fruit of . There is no limit to the amount of fruit each basket can hold .
2, You can choose any tree to start picking , You have to go from   Each tree   Trees （ Including the trees that start picking ） On   Just pick a fruit  . The fruit picked should match the type of fruit in the basket . Every time you pick , You will move right to the next tree , And continue to pick .
3, Once you get to a tree , But the fruit doesn't match the type of fruit in the basket , Then you must stop picking .

Give you an array of integers fruits , Return the fruit you can collect Maximum number .

The content of the topic is too misleading , Read the pen pal's explanation ： fruits The numbers in represent the type of fruit , Each basket can hold only one kind of Type of fruit , The essence of this problem is to find the longest subsequence that contains only two elements .

Test data
Input ：fruits = [1,2,1]
Output ：3
explain ： You can pick all 3 tree .

Input ：fruits = [1,2,3,2,2]
Output ：4
explain ： You can pick [2,3,2,2] These four trees .
If you start picking from the first tree , You can only pick [1,2] These two trees .

Input ：fruits = [3,3,3,1,2,1,1,2,3,3,4]
Output ：5
explain ： You can pick [1,2,1,1,2] These five trees .

Their thinking

Method ： The sliding window
Their thinking ： A little confused , Especially when dealing with shrinking windows , I don't know how to deal with ：
utilize map aggregate , Record the number of times each element , Added a judgment condition ：

//** Because considering map The size in , According to the title requirements , Put in one data at a time , Have to consider map Size , if map.size()>2, Will left Subtract one from the corresponding number ,left++, Continue to judge , until map.size()=2 when , Continue to expand the window , Put elements , Continue to judge .**
     while (map.size() > 2) {
             map.put(fruits[left], map.get(fruits[left]) - 1);
             if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
             left++;
         }
 

Simple illustration ：

Time complexity ： O(N) N It's an array fruits The length of
Spatial complexity ： O(N)

Code

Method ： The sliding window

public int totalFruit(int[] fruits) {
    
        if (fruits == null || fruits.length == 0) return 0;
        int n = fruits.length;
        Map<Integer, Integer> map = new HashMap<>();
        int maxLen = 0, left = 0;
        // Expand the window （right Move all the way to the right ）
        for (int i = 0; i < n; i++) {
    
            map.put(fruits[i], map.getOrDefault(fruits[i], 0) + 1); 
            // contract the window , Every time according to map.size() Size to shrink to move left
            while (map.size() > 2) {
     
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) map.remove(fruits[left]); 
                left++;
            }
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }

source ： Power button （LeetCode）
link ：link-904. Fruit baskets