[Leetcode]_121. Best Time to Buy and Sell Stock

문제

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150 

LeetCode - The World's Leading Online Programming Learning Platform

풀이

처음에는 이중반복문으로 풀었는데, 시간 초과가 발생하여 다른 방법을 생각해보았다.

 

투 포인터를 두고 left 포인터의 값과 right 포인터의 값을 뺀 값이 이익이라고 두는 것은 동일하다.

 

여기서 한가지 더 비교할 부분이 right 포인터의 값이 left 포인터의 값보다 작으면 left 포인터를 이동시켜주는 것이다.

 

왜냐하면, 이후의 left 포인터의 값은 가장 작으면 작을수록 싸게 산다는 의미이고 right 포인터의 값은 크면 클수록 비싸게 판다는 의미이기 때문에 right 포인터를 이동시키면서 left 포인터와 비교하여 left 포인터를 최솟값으로 유지 시켜주는 것이 시간 복잡도를 줄이는 관건이다.

 

def maxProfit(prices):
	left, right = 0, 1
    max_profit = 0
    
    while right < len(prices):
    	curr_profit = prices[right] - prices[left]
        if prices[left] < prices[right]:
        	max_profit = max(curr_profit, max_profit)
        else:
        	left = right
        right += 1
    return max_profit