[Dart] 121. Best Time to Buy and Sell Stock

1. 문제

 

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

 

 

 

2. 요구사항

1) 주식 가격이 작성된 prices 배열 주어진다.

2) 주식을 한 번 사고 한 번 팔아서 얻을 수 있는 최대 이익을 계산한다.

3) 이익을 얻을 수 없는 경우에는 0을 반환한다.

 

 

3. 핵심 아이디어

1) 최소 가격을 추적하고, 최대 이익 계산

prices 배열에서 가장 싼 가격(minPrice)을 추적한다.

 

배열을 왼쪽에서 오른쪽으로 순회하며 현재 가격 - minPrice 를 계산해서 현재 시점에서 얻을 수 있는 이익을 구한다.

 

그 이익이 지금까지 본 최대 이익보다 크다면 maxProfit에 저장한다.

 

 

2) 코드

class Solution {
  int maxProfit(List<int> prices) {
    int minPrice = 1 << 30; 	// 아주 큰 값으로 초기화 (2^30 ≈ 10억)
    int maxProfit = 0;         	// 최대 이익을 저장할 변수

    for (int price in prices) {
      // 더 작은 가격을 찾으면 minPrice를 갱신
      if (price < minPrice) {
        minPrice = price;
      }
      // 현재 이익이 기존 profit보다 크면 갱신
      else if (maxProfit < price - minPrice) {
        maxProfit = price - minPrice;
      }
    }

    return maxProfit; 				// 최대 이익 반환
  }
}

 

시간 복잡도 : O(n)

 - 한 번만 순회

 

공간 복잡도 : O(1)