ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນດ້ວຍຄ່າ ທຳ ນຽມໂອນ Leetcode


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

ບັນຫາບັນຫາ

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

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

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

  1. ພວກເຮົາບໍ່ສາມາດຊື້ຫຸ້ນ ໃໝ່ ໄດ້ຖ້າພວກເຮົາບໍ່ໄດ້ຂາຍຫຸ້ນກ່ອນ ໜ້າ ນີ້. ນັ້ນແມ່ນເວລາທີ່ພວກເຮົາສາມາດມີຫຸ້ນສ່ວນຫຼາຍໄດ້.
  2. ພວກເຮົາສາມາດເຮັດທຸລະ ກຳ ຫຼາຍຄັ້ງ.
  3. ທຸກໆຄັ້ງທີ່ພວກເຮົາເຮັດທຸລະ ກຳ ພວກເຮົາຕ້ອງຈ່າຍຄ່າ ທຳ ນຽມການເຮັດທຸລະ ກຳ.
  4. ໃນຊ່ວງເວລາທີ່ພວກເຮົາບໍ່ສາມາດຊື້ຫຸ້ນໄດ້ຫຼາຍກ່ວາ ໜຶ່ງ ຮຸ້ນ.

ຍົກຕົວຢ່າງ

prices = [1, 3, 2, 8, 4, 9], fee=2
8

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

ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນດ້ວຍຄ່າ ທຳ ນຽມໂອນ Leetcode

ວິທີການຂອງເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນດ້ວຍຄ່າ ທຳ ນຽມໂອນ Leetcode

ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາຕ້ອງໄດ້ຄິດກ່ຽວກັບວິທີທີ່ພວກເຮົາສາມາດຫາ ກຳ ໄລໄດ້ສູງສຸດໂດຍການຊື້ແລະຂາຍຫຸ້ນ. ນີ້ແມ່ນວິທີການເພື່ອໃຫ້ໄດ້ ກຳ ໄລສູງສຸດ:

  1. ພວກເຮົາຈະຊື້ຫຸ້ນໃນລາຄາຕໍ່າສຸດແລະຂາຍໃນລາຄາທີ່ສູງສຸດ.
  2. ຍ້ອນວ່າພວກເຮົາ ຈຳ ເປັນຕ້ອງຈ່າຍຄ່າ ທຳ ນຽມ ສຳ ລັບແຕ່ລະທຸລະ ກຳ, ສະນັ້ນ, ພວກເຮົາຈະຂາຍຫຸ້ນເທົ່ານັ້ນເມື່ອລາຄາຂາຍ> ລາຄາຕົ້ນທຶນ + ຄ່າ ທຳ ນຽມ.
  3. ເຖິງວ່າຈະຊອກຫາລາຄາຂາຍທີ່ດີທີ່ສຸດ, ພວກເຮົາຈະຂາຍຫຸ້ນເມື່ອພວກເຮົາພົບກັບລາຄາຂາຍ> ລາຄາຕົ້ນທຶນ + ຄ່າ ທຳ ນຽມ. ລາຄາຕົ້ນທຶນຈະກາຍເປັນລາຄາຕົ້ນທຶນ - ຄ່າ ທຳ ນຽມ.

ການປະຕິບັດ

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

//function to find maximum profit
#include <bits/stdc++.h> 
using namespace std; 
    int Profit(vector<int>& prices, int fee) {
        int n = prices.size();
        int ans = 0;
        int mn = prices[0];
        for(int i=0;i<n;i++)
        {
         if (prices[i] < mn)
                mn = prices[i];
         if(prices[i] > mn + fee)
         {
              ans += prices[i] - fee - mn;
              mn = prices[i] - fee;
         }
            
        }
           return ans;  
    }

int main() 
{ 
 vector<int> arr = {1, 3, 2, 8, 4, 9}; 
 int fee=2;
 cout<<Profit(arr,fee)<<endl; 
 return 0;
}
8

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

import java.util.Arrays; 
public class Tutorialcup {
 public static  int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int ans = 0;
        int mn = prices[0];
        for(int i=0;i<n;i++)
        {
         if (prices[i] < mn)
                mn = prices[i];
         if(prices[i] > mn + fee)
         {
              ans += prices[i] - fee - mn;
              mn = prices[i] - fee;
         }
            
        }
           return ans;  
    }
  public static void main(String[] args) {
    int [] arr = {1, 3, 2, 8, 4, 9}; 
    int fee=2;
    int ans=  maxProfit(arr,fee);
    System.out.println(ans);
  }
}
8

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

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

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

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

O (1) ເພາະວ່າພວກເຮົາໃຊ້ ໜ່ວຍ ຄວາມ ຈຳ ເທົ່ານັ້ນທີ່ຈະເກັບ ຄຳ ຕອບ.

ເອກະສານ