Leet Code 121. Best Time to Buy and Sell Stock

 

 

leetcode.com/problems/best-time-to-buy-and-sell-stock/

 

 

시간초과 (브루트포스)

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

시간복잡도 : O(N^2)

• 1 <= prices.length <= 10^5
• 최대 시간복잡도 : 10^10

 

알고리즘 개선

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        profit = 0
        
        i = 0 #박힌돌
        for j in range(len(prices)):#굴러들어온 돌
            
            #박힌돌보다 굴러들러온 돌이 더 작을 때
            if prices[i] >= prices[j] :
                i = j # 박힌돌 위치 이동
                
            #박힌돌보다 굴러들어온 돌이 더 클 때
            elif prices[j] - prices[i] > profit :
                profit = prices[j] - prices[i] # profit 계산
                
        return profit

시간복잡도 : O(N)

박힌돌 굴러들어온돌 개념 참고함 it-sunny-333.tistory.com/173