LeetCode Best Time to Buy and Sell Stock (JavaScript)

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

문제 설명

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

---

문제 풀이

1. (시간 초과)

최대 수익을 계산하기 위해 현재 값(i)와 i 이후의 배열의 최대 값을 구해서 계산하는 방식

prices에서 i 다음 값들 중 최대 값을 구하기 위해 `slice`를 통해 계산하는 방식은 총 O(n^2)의 시간 복잡도를 가지기 때문에

prices의 길이가 길면 시간 초과의 문제가 발생

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let profit = 0;

    for (let i = 0; i < prices.length; i++) {
        const price = Math.max(...prices.slice(i + 1));
        profit = Math.max(profit, price - prices[i]);
    }

    return profit;
};

 

2. (해결)

O(n)의 시간 복잡도로 문제를 해결할 수 있는 로직으로 수정

배열의 뒤 부터 계산하면서 최대 이윤을 계산하기 위해 maxPrice를 통해 현재 타겟이될 최대 값을 갱신하도록 함

이후 i번째와 maxPrice의 차이를 통해 최대 이윤 profit을 계산하도록 함

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let profit = 0;

    let maxPrice = prices[prices.length - 1];

    for (let i = prices.length - 2; i >=0; i--) {
        profit = Math.max(profit, maxPrice - prices[i]);

        maxPrice = Math.max(maxPrice, prices[i]);
    }

    return profit;
};

---

결론

최대 이윤을 계산하기 위해 maxPrice를 최대로 갱신해주는 부분이 이 문제를 해결하는 핵심부분