ผลไม้ใส่ตะกร้าใน C ++

สมมติว่าเรามีต้นไม้แถวหนึ่ง ต้นไม้ที่ i ให้ผลที่มีต้นไม้ประเภท[i] เราสามารถเริ่มต้นจากต้นไม้ใดก็ได้ที่เราเลือก แล้วทำตามขั้นตอนเหล่านี้ซ้ำๆ -

• เพิ่มผลไม้หนึ่งชิ้นจากต้นไม้ต้นนี้ลงในตะกร้าของเรา ถ้าไม่มีโอกาสก็หยุดเถอะครับ
• ย้ายไปที่ต้นไม้ถัดไปทางด้านขวาของต้นไม้ปัจจุบัน หากไม่มีต้นไม้อยู่ทางขวา ให้หยุด

เรามีตะกร้าสองใบ และตะกร้าแต่ละใบสามารถบรรทุกผลไม้ในปริมาณเท่าใดก็ได้ แต่เราต้องการให้ตะกร้าแต่ละใบใส่ผลไม้อย่างละประเภทเท่านั้น เราต้องหาจำนวนผลไม้ทั้งหมดที่เรารวบรวมได้ด้วยขั้นตอนนี้หรือไม่? ดังนั้นถ้าต้นไม้เป็นเหมือน [0, 1, 2, 2] ผลลัพธ์จะเป็น 3 เราสามารถรวบรวม [1,2,2] หากเราเริ่มจากต้นไม้ต้นแรกเราก็จะเก็บเพียง [0, 1]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดต้นไม้ j :=0, ans :=0
• สร้างหนึ่งแผนที่ m
• สำหรับ i ในช่วง 0 ถึง n – 1
  • เพิ่ม m[tree[i]] ขึ้น 1
  • ในขณะที่ขนาดของ m คือ> 2 และ j <=i แล้ว
    • ลด m[tree[j]] ลง 1
    • ถ้า m[tree[j]] =0 ให้ลบ tree[j] ออกจาก m
    • เพิ่ม j ขึ้น 1
  • ans :=สูงสุดของ i – j + 1 และ ans
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int totalFruit(vector<int>& tree) {
      int n = tree.size();
      int j = 0;
      map <int, int> m;
      int ans = 0;
      for(int i = 0; i < n; i++){
         m[tree[i]] += 1;
         while(m.size() > 2 && j <= i){
            m[tree[j]]--;
            if(m[tree[j]] == 0)m.erase(tree[j]);
            j++;
         }
         ans = max(i - j + 1, ans);
      }
      return ans;
   }
};
main(){
   vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
   Solution ob;
   cout <<(ob.totalFruit(v));
}

อินพุต

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

ผลลัพธ์

5