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

❒ Description

---

제목	Best Time to Buy and Sell Stock
링크	https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
자료구조	선형 자료구조
풀 날짜	07/24

 

 

 

 

❒ Solution

---

public static int maxProfit(int[] prices) {
    int maxProfit = 0;
    int minPrice = prices[0];

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        maxProfit = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

 

이 문제는 임의로 maxProfit과 minPrice를 설정하여 시작하는 문제이다.

모든 경우를 확인하는 Brute Force 방식으로는 timeout이 발생한다.

위와 같이 해결할 경우 O(n)의 시간 복잡도로 문제를 해결할 수 있다.