[LeetCode] 121 Best Time to buy and Sell Stock

date

‣

slug

leetcode-121

author

status

Public

문제 링크

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

문제

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 dayto buy one stock and choosing a different day in the futureto sell that stock.

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

문제풀이

간단한 Greedy 문제입니다.

Buy price와 sell price를 갱신해 나가고

buy price가 갱신될 때 그 떄의 buy와 sell의 차를 기록합니다.

마지막에 buy와 sell차이를 기록하고

기록 된 모든 값의 max값을 리턴합니다.

파이썬 문제풀이 코드


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        buy_price = float('inf')
        sell_price = 0
        sell_price_lst = []

        for price in prices:
            if buy_price > price:
                sell_price_lst.append(sell_price - buy_price)
                buy_price = price
                sell_price = buy_price

            if sell_price < price:
                sell_price = price
            
        sell_price_lst.append(sell_price - buy_price)
            
        return max(sell_price_lst)

시간복잡도

입력

Constraints:

1 <= prices.length <= 10^5

0 <= prices[i] <= 10^4

출력

int

예제 입력


prices = [7,1,5,3,6,4]

예제 출력


prices = [7,6,4,3,1]

알고리즘 분류

그리디