[LeetCode] 121. Best Time to Buy and Sell Stock (JS)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

핵심 아이디어

• Sliding window - left, right pointer(index) 이용하여 지역값 구하고, 저장된 max와 비교.
• 매번 right pointer를 움직이지만, profit 조건이 깨지면 left = right로 초기화
  • profit < 0 될 때의 right가 sliding window 내의 지역 최솟값이기 때문
• 항상 right - left로 계산해야 하고 (과거로 돌아가서 팔 수 없다), 최솟값이 바뀔 때 마다 계산 기준이 바뀜

 

복잡도

• 시간 복잡도: O(n)
  
  • right pointer가 배열 0번부터 n번째 까지 가는데 걸리는 시간
• 공간 복잡도: O(1)
  
  • right, left pointer만 만들고 별도의 배열을 생성하지 않음.

 

설명

날짜별 주식 가격이 주어졌을 때, 얻을 수 있는 최대 이익을 계산하는 문제이다. 과거로 돌아가서 팔 수 없기 때문에 max(prices) - min(prices)로는 문제를 해결할 수 없다. 그렇게 풀면 최댓값이 최솟값보다 더 과거일 때 잘못된 답을 내놓는다.

핵심은 지역 최솟값을 기준으로 이익을 계산하고, 그 중에서 최대 이익을 저장하는 것이다. 그래서 최솟값이 바뀔 때 left pointer가 움직이는 sliding window 기법을 사용했다. right가 left보다 낮을 때 left를 right로 바꾸는 이유는 나중에 더 높은 right가 나와도, 더 낮은 left를 기준으로 계산하는 것이 항상 유리하기 때문이다.

 

코드 (Javascript)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxP = 0;
    let buyDay = 0;
    let sellDay = 0;
    
    while(sellDay < prices.length) {
        const profit = prices[sellDay] - prices[buyDay];
        
        if(profit > 0) {
            maxP = Math.max(profit, maxP);
        } else {
            buyDay = sellDay;
        }
        
        sellDay += 1;
    }
    
    return maxP;
};

 

유튜브 NeetCode 해설 영상