LeetCode 문제 : 주식을 사고 파는 가장 좋은 시기

저는 최근 "주식을 사고 파는 가장 좋은 시기"라는 고전적인 LeetCode 문제를 다루었습니다. 이 문제는 주식을 한 번 사고 팔 때 얻을 수 있는 최대 이익을 구하는 문제입니다. 제가 탐구한 다양한 접근 방식과 그 복잡성을 자세히 살펴보겠습니다. 문제의 URL은 다음과 같습니다.

리트코드 121

무차별 접근 방식(시간 복잡도: O(n^2))

가장 간단한 해결책은 배열의 모든 요소를 ​​나머지 모든 요소와 비교하는 것입니다. 각 가격에 대해 나중에 판매할 경우 얻을 수 있는 이익을 계산합니다. 그런 다음 발생한 최대 이익을 추적합니다. 그러나 이 접근 방식은 시간 복잡성이 높고 시간 제한 초과가 발생했습니다.

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

    let max = 0;
    for (var i = 0; i  a) return b - a;
    else return 0;
}

이유는 다음과 같습니다. 각 요소를 n-1개의 다른 요소와 비교하여 n*(n-1)/2 비교 결과를 얻습니다. 이는 대략 O(n^2) 시간 복잡성으로 해석되며, 이는 대규모 데이터 세트에 대해서는 비효율적입니다. 불행하게도 이 접근 방식은 LeetCode에서 "Time Limit Exceeded" 오류로 이어지는 경우가 많습니다.

두 포인터 접근법(시간 복잡도: O(n))

효율성을 높이기 위해 판매하기 전에 구매한다는 사실을 활용할 수 있습니다. 두 가지 지침을 소개할 수 있습니다:

• 구매: 현재 잠재 구매 가격을 나타냅니다.
• sell: 판매 가격 후보를 가리킵니다.

세 번째 요소부터 가격 배열을 반복하는 것이 아이디어입니다(처음 두 요소는 구매 및 판매에 사용되므로). 매도가(현재 요소)와 매수가의 차이가 현재 최대 이익보다 큰지 지속적으로 확인합니다. true인 경우 최대 이익을 업데이트합니다. 그렇지 않으면 매수 포인터를 현재 요소(잠재적으로 더 낮은 매수 가격)로 업데이트하고 매도 포인터를 한 단계 앞으로 이동합니다.

이 접근 방식은 배열을 한 번만 반복하므로 시간 복잡도가 크게 향상되어 O(n)에 도달합니다.

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



<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172284027594031.png?x-oss-process=image/resize,p_40" class="lazy" alt="LeetCode 문제 : 주식을 사고 파는 가장 좋은 시기" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<h2>
  
  
  Python 예제를 사용한 탐욕스러운 접근 방식(시간 복잡도: O(n))
</h2>

<p>탐욕스러운 접근 방식을 사용하면 비슷한 시간 복잡도를 달성할 수 있습니다. 여기서 핵심은 낮은 가격에 사서 높은 가격에 판매해야만 최대 이익을 얻을 수 있다는 점을 이해하는 것입니다.  따라서 가격 배열을 반복하고 지금까지 발생한 최소 가격을 추적할 수 있습니다. 이는 잠재적 구매 가격을 나타냅니다.</p>

<p>다음은 탐욕적 접근 방식을 Python으로 구현한 것입니다.<br>
</p>

<pre class="brush:php;toolbar:false">class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0;
        min_buy = float('inf')
        for price in prices:
            min_buy = min(min_buy , price )
            max_profit =  max(max_profit, price-min_buy)
        return max_profit

내 포트폴리오에서 저를 찾을 수 있는 다른 곳은 여기에서 언제든지 자세히 알아볼 수 있습니다

위 내용은 LeetCode 문제 : 주식을 사고 파는 가장 좋은 시기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!