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


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon DE Shaw ເຟສບຸກ Microsoft Morgan Stanley Uber
Array ຄວາມໂລບມາກ

ບັນຫາບັນຫາ

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

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

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

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

ຍົກຕົວຢ່າງ

prices = [7,1,5,3,6,4]
7

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

ມື້ ທຳ ອິດ: ພັກຜ່ອນ

ມື້ທີສອງ: ຊື້

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

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

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

ມື້ທີຫົກ: ພັກຜ່ອນ

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

ຍ້ອນວ່າພວກເຮົາບໍ່ມີຂໍ້ ຈຳ ກັດກ່ຽວກັບ ຈຳ ນວນການໂອນເງິນດັ່ງນັ້ນພວກເຮົາຈະຄິດເຖິງກ algorithm ໂລຫິດ ທີ່ນີ້. ສະນັ້ນທຸກໆຄັ້ງທີ່ພວກເຮົາຈະຊື້ຫຸ້ນໃນລາຄາຕ່ ຳ ສຸດແລະຂາຍໃນລາຄາທີ່ສູງສຸດ. ພວກເຮົາສາມາດສະຫຼຸບມັນໄດ້, ໃນແຕ່ລະ minima ພວກເຮົາຈະຊື້ຫຸ້ນແລະໃນແຕ່ລະ maxima, ພວກເຮົາຈະຂາຍຫຸ້ນ. ນີ້ໄດ້ຖືກອະທິບາຍໃນຮູບທີ່ໃຫ້ໄວ້ຂ້າງລຸ່ມນີ້. ມັນແມ່ນດິນຕອນ ໜຶ່ງ ລະຫວ່າງລາຄາຫຸ້ນແລະມື້. ການແກ້ໄຂ leetcode ກັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຮຸ້ນ II

ພວກເຮົາສາມາດເຮັດໃຫ້ມັນລຽບງ່າຍຖ້າພວກເຮົາສັງເກດເຫັນວ່າ maxima ໄດ້ຖືກສ້າງຕັ້ງຂື້ນເມື່ອມີຄ່ານ້ອຍໆຖືກເພີ່ມເຂົ້າ minima. ສະນັ້ນເຖິງວ່າຈະມີການຕິດຕາມທຸກໆ minima ແລະ maxima ເພື່ອຄິດໄລ່ ກຳ ໄລສູງສຸດ, ພວກເຮົາສາມາດເພີ່ມຄ່າເຫຼົ່ານັ້ນເຂົ້າໃນຜົນ ກຳ ໄລຂອງພວກເຮົາເຊິ່ງພວກເຮົາພົບວ່າຄ້ອຍບວກທີ່ເປັນລາຄາ [i]> ລາຄາ [i-1]. ການເພີ່ມເຕີມຂອງຄຸນຄ່າດັ່ງກ່າວຈະຊ່ວຍໃຫ້ພວກເຮົາມີ ກຳ ໄລສູງສຸດ.

ການແກ້ໄຂ leetcode ກັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຮຸ້ນ II

ການປະຕິບັດ

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

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 7,1,5,3,6,4 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
7

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

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

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

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

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

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

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (1) ເພາະວ່າພວກເຮົາໃຊ້ ໜ່ວຍ ຄວາມ ຈຳ ເທົ່ານັ້ນທີ່ຈະເກັບ ຄຳ ຕອບ.

ເອກະສານ