[NeetCode/Python] Buy and Sell Crypto

문제 링크: https://neetcode.io/problems/buy-and-sell-crypto

NeetCode

 

투 포인터/슬라이딩 윈도우

 

[내 풀이]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        for i in range(len(prices)-1):
            for j in range(i, len(prices)):
                profit = prices[j] - prices[i]
                if profit > maxProfit:
                    maxProfit = profit

        return maxProfit

 

비효율적인 코드.. 그냥 범위가 작아서 쓸수 있는 코드...

 

 

[솔루션]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        
        lowest = prices[0]
        for price in prices:
            if price < lowest:
                lowest = price
            res = max(res, price - lowest)
        return res

 

 

시간 복잡도

n이 prices의 길이일 때,

내 코드: O(n^2)

솔루션: O(n)