Best Time to Buy and Sell Stock - LeetCode

Problem

1. input: 주식의 시간별 가격이 담긴 리스트 prices
2. output: 주식을 사고 팔았을 때 얻을 수 있는 최대 수익 리턴
3. 주식은 같은 시간에 사고, 바로 팔 수 없음
   • 1 <= prices.length <= 10^5
   • 0 <= prices[i] <= 10^4

Idea

주어진 가격 리스트를 순회하며, 최솟값을 갱신하고 (가격 - 최솟값)의 최댓값을 찾으면 된다.

Solution

1. 사실상 구현

   배열 순회

   가격의 최솟값 갱신

   (현재 가격 - 최솟값)의 최댓값 갱신

   class Solution {
       fun maxProfit(prices: IntArray): Int {
           var answer = 0
           var low = prices[0]
           for (idx in 1 until prices.size) {
               low = minOf(low, prices[idx]) // 최솟값 갱신 (구입 가격)
               if (prices[idx] <= answer) continue
               answer = maxOf(answer, prices[idx] - low) // 최대 수익 갱신
           }
           return answer
       }
   }
   

   시간 복잡도: 배열 순회 = n

   

Point