Trái cây vào giỏ trong C++

Cho hàng cây, cây i cho trái cây loại tree[i]. Có 2 giỏ, mỗi giỏ chỉ chứa 1 loại trái cây. Bắt đầu từ cây bất kỳ, đi sang phải, thu thập trái cây. Tìm số lượng tối đa có thể thu được.

Ví dụ: [0,1,2,2] → 3 (thu [1,2,2] từ cây 1).

Thuật toán giải quyết (Cửa sổ trượt + Hash Map)

Tìm đoạn con dài nhất chứa tối đa 2 giá trị khác biệt.

1. j = 0, ans = 0, map m đếm tần suất.
2. Duyệt i = 0 .. n-1:
   • m[tree[i]]++.
   • Trong khi m.size() > 2:
     • m[tree[j]]--; nếu bằng 0 → xóa.
     • j++.
   • ans = max(ans, i - j + 1).
3. Trả về ans.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int n = tree.size(), j = 0, ans = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {
            m[tree[i]]++;
            while (m.size() > 2) {
                if (--m[tree[j]] == 0) m.erase(tree[j]);
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

int main() {
    vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
    Solution ob;
    cout << ob.totalFruit(v);
}

Đầu vào

[3,3,3,1,2,1,1,2,3,3,4]

Đầu ra

5