[Leetcode] 121. Best Time to Buy and Sell Stock - JS

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

 

1. 문제 분석

문제분석
--------------------
- 정수 배열 prices
    - prices[i]는 i 번째 일의 주식 가격
- 어느 하루에 주식을 사서 다른 날에 팔아 최대의 이익을 내고 싶다.
- 이 때 최대 이익을 반환하라.

제한조건
--------------------
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4

 

2. 접근 방법

접근방법
--------------------
배열 요소에서 사는 날까지 순회하여 중첩 반복문을 만들 필요가 없다.

1. 배열을 n회만 순회하여, 파는 날을 가지고 이익을 계산한다.
2. 이익은 현재 반복문에서 구한 값과 이전에 등록된 값 중 큰 값을 할당한다.
3. 만약 파는 날 가격이 사는 날 가격보다 저렴하면 이 날 사면된다.

 

3. 코드

var maxProfit = function(prices) {
    let buyPrice = prices[0];
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        const sellPrice = prices[i];
        profit = Math.max(profit, sellPrice - buyPrice);
        buyPrice = Math.min(buyPrice, sellPrice)
    }
    return profit;
};

 

4. 복잡도 분석

시간 복잡도: O(n)

공간 복잡도: O(1)