Leetcode — 탑 인터뷰 –. 주식을 사고 파는 가장 좋은 시기

다음과 같이 설명하면 문제가 쉽습니다.

가격[i]이 i번째 날 특정 주식의 가격인 배열 가격이 제공됩니다.

특정 주식을 매수할 하루를 선택하고 해당 주식을 판매할 미래의 다른 날을 선택하여 수익을 극대화하고 싶습니다.
이 거래에서 얻을 수 있는 최대 이익을 반환합니다. 수익을 얻을 수 없으면 0을 반환하세요.

예 1:

입력: 가격 = [7,1,5,3,6,4]
출력: 5

설명: 2일차 매수(가격 = 1), 5일차 매도(가격 = 6), 이익 = 6-1 = 5.
판매하기 전에 구매해야 하기 때문에 2일차 구매와 1일차 판매는 허용되지 않습니다.

예 2:

입력: 가격 = [7,6,4,3,1]
출력: 0

설명: 이 경우 거래가 이루어지지 않으며 최대 이익 = 0입니다.

제약조건:

1 <= 가격.길이 <= 105
0 <= 가격[i] <= 104

처음에는 정렬하고 더 작은 숫자와 더 큰 숫자를 가져오는 것에 대해 생각할 수 있지만 배열에서 그 전후에 다른 범위나 숫자를 얻을 수 있으므로 차이가 예상한 것과 일치하지 않을 수 있으므로 정렬을 잊어버리세요.

이 경우를 해결하는 좋은 방법은 배열을 반복하면서 최소값과 최대값, 차이를 고려하는 것입니다. 최소값이 예상보다 작으면 모든 것을 재설정하세요. 그렇지 않으면 계속 진행하여 최대값보다 작을 때 최대값을 업데이트하고 항상 최대값뿐만 아니라 차이도 얻습니다. 그렇지 않으면 최소값이 작아지지만 최대값이 크지 않으면 실패할 수 있습니다. .

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int max = prices[0];
        int diff = 0;

        for(int i=1;i prices[i]){
                min = prices[i];
                max = prices[i];
            } else if (max < prices[i]) {
                max = prices[i];
            }

            if(diff < (max - min)) {
                diff = max - min;
            }
        }

        return diff;
    }
}






런타임: 2ms, 주식 매매 최적 시간에 대한 Java 온라인 제출의 77.66%보다 빠릅니다.

메모리 사용량: 61.4MB, 주식 매매 최적 시점에 대한 Java 온라인 제출의 80.34% 미만.


최소값을 제거하고 최대값만 사용하여 더욱 개선할 수 있지만 그 차이는 큰 문제가 아니지만 그럼에도 불구하고 성능이 향상됩니다.

—

그렇습니다! 논의할 다른 사항이 있으면 언제든지 댓글을 남겨주세요. 누락된 사항이 있으면 알려주시면 그에 따라 업데이트할 수 있습니다.

다음 포스팅까지! :)


          

            
        
위 내용은 Leetcode — 탑 인터뷰 –. 주식을 사고 파는 가장 좋은 시기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!