[LeetCode] 121. Best Time to Buy and Sell Stock

코드

배열의 길이가 10만이기 때문에 2중 for문으로 풀이하는 건 불가능. O(N)에 풀이될 수 있어야 한다.

배열을 한 번만 탐색하면서 최대의 차이값을 구하기 위해서는 매번 작은 값과 차이값을 둘 다 갱신하면 된다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
    	# min_price : 배열의 최저값
        # ans : 차이의 최대값
        min_price, ans = prices[0], 0
        
        for i in range(1, len(prices)):
            min_price = min(min_price, prices[i])
            ans = max(ans, prices[i]-min_price)
        
        return ans