Leetcode_121. Best Time to Buy and Sell Stock

Problem

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

Intuition

반복문으로 최소값과 최대값 차이를 변수에 저장하고 이 변수보다 큰 차이가 나올 때마다 지속 최신화시켜주다가 마지막에 이를 리턴하면 되지 않을까

Approach

이중 반복문, Max.max를 사용해보았지만 시간 복잡도 문제로 실패.

min, max 변수로 접근하는건 동일하되, 더 작은 min 값이 발견될 때는 min값만 업데이트 해주고, min보다 큰 수가 나올 때는 현재값과 min의 차이를 비교한 수가 max(최대 차이) 보다 클 경우 업데이트해주는 방식으로 해결.

Complexity

• Time complexity: O(n). 반복문 1회
• Space complexity: O(1). 변수 2개만 사용

Code

/**
 * @param {number[]} prices
 * @return {number}
 */

// // first try - failed for time limit
// var maxProfit = function(prices) {
//   let maxProfit = 0;

//   for(let i = 0; i < prices.length; i++) {
//       for(let j = i + 1; j < prices.length; j++) {
//           const diff = prices[j] - prices[i];
//           if(diff > maxProfit) maxProfit = diff 
//       }
//   }  
//   return maxProfit;
// };

// second try - Math.max로 최대값 구해서 비교하기
// var maxProfit = function(prices) {
//   let maxProfit = 0;

//   for(let i = 0; i < prices.length; i++) {

//     let curPrice = prices[i];
//     let maxPrice = Math.max(...prices.slice(i+1))
//     let diff = maxPrice - curPrice;

//     if(diff > maxProfit) {
//       maxProfit = diff
//     }
//   }  
//   return maxProfit;
// };

var maxProfit = function(prices) {
  let min = Infinity;
  let max = 0;

  prices.forEach(el => {
    if(el < min) {
      min = el
    } else if(el - min > max) {
      max = el - min
    }
  })
  return max
};