Day007 - 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

내 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0            # profit을 0으로 설정
        buy_price = prices[0] # 구매가격을 첫째날의 가격으로 설정

        for sell_price in prices[1:]:
            if sell_price > buy_price:	# 판매가가 구매가보다 비싸다면
                profit = max(profit, sell_price - buy_price) # "판매가 - 구매가"와 현재까지의 최대 profit을 비교하여 더 큰 값을 profit으로 설정 
            else:
                buy_price = sell_price # 판매가가 구매가보다 싸다면 더 싼 구매가로 갱신

        return profit

주어진 stock의 prices중에서 가장 큰 이득을 볼 수 있는 구매/판매 시기를 구하는 문제이다.

가장 먼저 떠오르는건 2-pointer를 사용해서 list에 존재하는 모든 경우의 수를 확인해보는 건데 이럴경우에 시간복잡도가 \(O(N^2)\)이 되어 시간초과로 통과할 수 없게 된다.

따라서 시간복잡도를 줄이는 방법이 이 문제의 핵심이라고 할 수 있다.

1. 주식의 구매시기는 판매시기보다 반드시 빨라야 한다.
2. 1번 조건이 있을 때 최저 구매가격을 구하면 나머지 모든 경우의 수를 확인할 필요가 없어진다.

위의 두 가지 조건을 이용하여 간단하게 코드를 작성하였다.

# Time Complexity : \(O(N)\)