JavaScript LeetCode 주식을 사고 팔기 가장 좋은 시간

즉각적인

price[i]가 i번째 날에 주어진 주식의 가격인 배열 가격이 주어집니다.

한 주식을 사는 날을 선택하고 그 주식을 팔기 위해 미래의 다른 날을 선택하여 이익을 최대화하려고 합니다.

이 거래에서 얻을 수 있는 최대 이익을 반환합니다. 이익을 얻을 수 없으면 0을 반환합니다.

예 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.

문제 분석

이전 문제와 마찬가지로 첫 번째 명백한 솔루션은 무차별 대입 솔루션을 사용하는 것입니다. 여기서 우리는 배열을 두 번 반복하여 모든 후속 값 사이의 모든 빼기를 확인하고 가장 높은 이익을 얻습니다.

이에 대한 시각적 예는 다음과 같습니다.

첫 번째 솔루션

계속해서 위에서 언급한 코드를 작성해 보겠습니다.

function maxProfit(prices) {
  let profit = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const currentProfit = prices[j] - prices[i]

if (currentProfit > profit ) {
        profit = currentProfit
      }
    }
  }

return profit;
}

여기에서 배열의 다음 요소의 가격을 현재와 비교합니다. 이것을 개념화하는 가장 좋은 방법은 i가 인덱스이고 j가 반복을 계속하는 포인터라는 것입니다.

최대 이익을 찾기 위해 두 개의 for 루프를 사용합니다. 이것은 O(n^2)의 복잡도를 가질 것입니다. 이것은 매우 느리기 때문에 꽤 큰 문제입니다! 그러나 어레이를 한 번만 반복하여 이를 최적화할 수 있습니다.

두 번째 솔루션

그러나 단일 반복은 어떻게 생겼습니까?

코드를 사용하면 다음과 같이 보일 것입니다.

var maxProfit = function(prices) {
    let profit = 0;

let stockToBuy = prices[0];

for(let i = 1; i < prices.length; i++) {
        if (stockToBuy > prices[i]) {
            stockToBuy = prices[i]
        }

const currentProfit = prices[i] - stockToBuy;

if (currentProfit > profit) {
            profit = currentProfit;
        }
    }

return profit;
};

배열의 첫 번째 요소에서 초기 stockToBuy를 가져옵니다. 그런 다음 배열에 대해 반복을 시작할 수 있습니다(첫 번째 건너뛰기). 다음 주식이 현재 선택한 주식보다 높은 가격인지 비교합니다. 그렇다면 더 높은 수익을 얻을 수 있으므로 전환합니다.

그러나 이것은 재설정 메커니즘으로도 사용됩니다. 주식의 가치가 더 높으면 이 시점부터 이전에 선택한 주식보다 더 높은 이익을 얻지 못할 것이라는 것을 알고 있습니다.

stockToBuy = prices[i]

그런 다음 새로운 currentProfit을 계산합니다. 이것은 현재 반복의 임시 값일 뿐입니다.

const currentProfit = prices[i] - stockToBuy;

그런 다음 for 루프 외부에 저장한 값과 비교합니다. 더 높으면 그것이 바로 우리가 원하는 것입니다.

처음에는 0으로 변수를 만들었으므로 이익을 찾지 못하면 그대로 반환할 수 있습니다.

욕심 많은 알고리즘

그런데 이것을 무엇이라고 합니까?

여기서 우리가 하고 있는 것은 모든 반복에서 최상의 옵션을 선택하고 과거 선택을 잊어버리는 것입니다. 이것을 탐욕 알고리즘이라고 합니다.

더 자세히 읽고 싶다면 여기Wikipedia article가 있습니다.

연결하자

이것이 마음에 들면 언제든지 저와 연결하거나

내 newsletter 에서 무료 개발자 로드맵과 주간 기술 산업 뉴스를 확인하십시오.