728x90
1. 문제
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)
728x90
'Programming > LeetCode' 카테고리의 다른 글
| [Dart] 136. Single Number (0) | 2025.03.26 |
|---|---|
| [Dart] 125. Valid Palindrome (0) | 2025.03.25 |
| [Dart] 104. Maximum Depth of Binary Tree (0) | 2025.03.21 |
| [Dart] 88. Merge Sorted Array (0) | 2025.03.20 |
| [Dart] 58. Length of Last Word (0) | 2025.03.19 |