ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon Goldman Sachs Yahoo
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ບັນຫາບັນຫາ

ໃນບັນຫາ“ ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown” ພວກເຮົາໄດ້ຮັບແຖວທີ່ແຕ່ລະອົງປະກອບໃນແຖວມີລາຄາຂອງຮຸ້ນໃນມື້ນັ້ນ.

ບໍ່ມີຂໍ້ ຈຳ ກັດ ຈຳ ນວນການເຮັດທຸລະ ກຳ. ຄຳ ນິຍາມຂອງການເຮັດທຸລະ ກຳ ແມ່ນການຊື້ຫຸ້ນ ໜຶ່ງ ສ່ວນແລະຂາຍຫຸ້ນ ໜຶ່ງ ສ່ວນ.

ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາ ກຳ ໄລສູງສຸດພາຍໃຕ້ຂໍ້ ຈຳ ກັດດັ່ງຕໍ່ໄປນີ້:

  1. ພວກເຮົາບໍ່ສາມາດຊື້ຫຸ້ນ ໃໝ່ ໄດ້ຖ້າພວກເຮົາບໍ່ໄດ້ຂາຍຫຸ້ນກ່ອນ ໜ້າ ນີ້. ນັ້ນແມ່ນເວລາທີ່ພວກເຮົາສາມາດມີຫຸ້ນສ່ວນຫຼາຍໄດ້.
  2. ຖ້າພວກເຮົາຂາຍຫຸ້ນໃນມື້ນັ້ນພວກເຮົາບໍ່ສາມາດຊື້ຫຸ້ນໃນວັນທີ (i + 1). ນັ້ນແມ່ນເວລາ 1 ວັນຂອງໄລຍະເວລາຮ່ວມມື

ຍົກຕົວຢ່າງ

prices = [1,2,3,0,2]
3

ຄໍາອະທິບາຍ: ກຳ ໄລສູງສຸດທີ່ສາມາດໄດ້ຮັບແມ່ນ 3. ລາຍລະອຽດຂອງການເຮັດທຸລະ ກຳ ດັ່ງຕໍ່ໄປນີ້:

ມື້ ທຳ ອິດ: ຊື້

ມື້ທີສອງ: ຂາຍ

ມື້ທີສາມ: cooldown

ມື້ທີສີ່: ຊື້

ມື້ທີຫ້າ: ຂາຍ

ວິທີການໃຊ້ເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown Leetcode Solution

ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາ ຈຳ ເປັນຕ້ອງສັງເກດບາງຢ່າງ:

  1. ທຸກຄັ້ງທີ່ພວກເຮົາຕ້ອງການຂາຍຫຸ້ນພວກເຮົາຕ້ອງໄດ້ຊື້ຫຸ້ນກ່ອນ ໜ້າ ນີ້. ໝາຍ ຄວາມວ່າການຂາຍຫຸ້ນແມ່ນຂື້ນກັບການຊື້ຫຸ້ນ.
  2. ມື້ ໜຶ່ງ ຂອງໄລຍະເວລາຮ່ວມມືແມ່ນສິ່ງທີ່ຕ້ອງເຮັດ. ສະນັ້ນການຊື້ຫຸ້ນແມ່ນຂື້ນກັບໄລຍະເວລາຮ່ວມມື.

ການຈື່ ຈຳ ຈຸດເຫຼົ່ານີ້ພວກເຮົາສາມາດ ກຳ ນົດລັດ:

  • ລັດ-A: ໃນລັດນີ້, ພວກເຮົາສາມາດຊື້ຫຸ້ນຫຼືພຽງແຕ່ພັກຜ່ອນ.
  • STATE-B: ຫຼັງຈາກຊື້ຫຸ້ນພວກເຮົາສາມາດຂາຍຫຸ້ນໄດ້ຫຼືຊື້ສ່ວນທີ່ເຫຼືອ.
  • ລັດ STATE-C: ນີ້ແມ່ນລັດທີ່ມີການຮ່ວມມື. ເມື່ອໄລຍະເວລາ cooldown ສິ້ນສຸດລົງແລ້ວພວກເຮົາຍ້າຍໄປ STATE-A.

ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown

ສາຍພົວພັນລະຫວ່າງສາມລັດເຫຼົ່ານີ້ສາມາດປ່ຽນເປັນ an ການສະແດງອອກຂອງພຶດຊະຄະນິດ ບ່ອນທີ່ STATE-X [i] ເປັນຕົວແທນໃຫ້ ກຳ ໄລສູງສຸດຈົນກ່ວາມື້ ໜຶ່ງ ຢູ່ທີ່ລັດ x.

sa->STATE-A,sb->STATE-B,sc->STATE-C
 sa[i]=max(sa[i-1],sc[i-1]);
 sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
 sc[i]=sb[i-1]+prices[i];

ຫຼັງຈາກ n iteration, ຜົນ ກຳ ໄລສູງສຸດຈະເປັນສູງສຸດ (sa [n-1], sc [n-1]) ເພາະວ່າຍ້ອນວ່າພວກເຮົາຕ້ອງການຜົນ ກຳ ໄລສູງສຸດດັ່ງນັ້ນພວກເຮົາຈະບໍ່ຢຸດຊື້ຫຸ້ນແລະບໍ່ຂາຍມັນ.

ຄະດີພື້ນຖານ:

sa[0]=0;
sb[0]=-prices[0]
sc[0]=INT_MIN

ການປະຕິບັດ

ລະຫັດ C ++ ສຳ ລັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<1)return 0;
       int sa[n],sb[n],sc[n];
        sa[0]=0,sb[0]=-prices[0],sc[0]=INT_MIN;
        for(int i=1;i<n;i++)
        {
            sa[i]=max(sa[i-1],sc[i-1]);
            sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
            sc[i]=sb[i-1]+prices[i];
        }
        return max(sa[n-1],sc[n-1]);  
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,0,2 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
3

ລະຫັດ Java ສຳ ລັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxProfit(int[] prices) {
          int n=prices.length;
    if(n<1)return 0;
    int[] sa = new int[n];
    int[] sb = new int[n];
    int[] sc = new int[n];
    sa[0] = 0;sb[0] = -prices[0]; sc[0] = Integer.MIN_VALUE;

    for (int i = 1; i < n; ++i) {
      sa[i] = Math.max(sa[i-1],sc[i-1]);
      sb[i] = Math.max(sb[i-1],sa[i-1]-prices[i]);
      sc[i] = sb[i-1]+prices[i];
    }

    return Math.max(sa[n-1],sc[n-1]);  
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,0,2}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
3

ການວິເຄາະຄວາມສັບສົນຂອງເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນກັບ Cooldown Leetcode Solution

ຄວາມສັບສົນເວລາ

ຄວາມສັບສົນຂອງເວລາຂອງລະຫັດຂ້າງເທິງແມ່ນ O (n) ເພາະວ່າພວກເຮົາ ກຳ ລັງປ່ຽນເສັ້ນທາງລາຄາພຽງຄັ້ງດຽວ. ນີ້ n ແມ່ນຄວາມຍາວຂອງອາໄລ່ລາຄາ.

ຄວາມສັບສົນໃນອະວະກາດ

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (n) ເພາະວ່າພວກເຮົາໃຊ້ອາເລເພື່ອເກັບຂໍ້ມູນຂອງລັດຕ່າງໆ.

ເອກະສານ