Easy - Best Time to Buy and Sell Stock

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

Best Time to Buy and Sell Stock - LeetCode

문제 설명

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.

 

Constraints:

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

예시

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.

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

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r, cur, univ = 0, 1, 0, 0
        length = len(prices)
        while l < length and r < length:
            cur = prices[r] - prices[l]

            if cur < 0:
                l = r
                r += 1
                continue
            
            if cur > univ:
                univ = cur
            r += 1

        return univ

슬라이딩 윈도우 문제.

주식을 산 이후의 날짜에 판매가 가능하므로 슬라이딩 윈도우의 양쪽 끝 인덱스를 담당하는 l 과 r은 아래와 같은 조건을 가지게 된다:

0 < l < r < length

 

모든 날짜를 탐색하고 constraint를 만족하기 위해서 l = 0, r = 1로 초기 설정한다.

 

l과 r이 위의 조건을 만족하는 동안 아래와 같은 로직을 따른다:

l에 주식을 사서 r에 주식을 판 수익 (prices[r] - prices[l]) 을 구한다.

수익이 음수일 경우 r, 주식을 판 날의 가격이 l, 주식을 산 날의 가격보다 낮다 == r에 주식을 사는 게 더 낫다. 가 되므로

l = r

r = r + 1

로 설정하고 넘어간다.

 

만약 현재 조건의 수익이 음수가 아니라면, 지금까지 최대 수익 (univ)와 비교하고 현재 조건의 수익이 지금까지의 최대 수익이 된다.

그리고 더 넓은 범위를 탐색하기 위해서 r = r + 1로 설정한다.

 

조건에 맞는 모든 범위를 탐색했다면 현재까지의 최대 수익 univ가 정답이 된다.