Leetcode 9월 Day18

문제 -

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

예시
""
입력: [7,1,5,3,6,4]
출력: 5
설명: 2일차에 매수(가격 = 1)하고 5일차에 매도(가격 = 6), 이익 = 6-1 = 5.
판매 가격이 구매 가격보다 커야 하므로 7-1 = 6이 아닙니다.
""
해결책

접근 방식 - deque 사용 deque를 사용하여 오른쪽의 최대 가격을 추적합니다. 그런 다음 다시 반복하고 최대 이익을 업데이트합니다.
TC = O(nlogn)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # we can use stack based approach
        stack = []
        ans = [0] * len(prices)
        for i in range(len(prices)-1, -1, -1):
            if i == len(prices)-1:
                stack.append(prices[i])
                continue
            while True:
                if prices[i] > stack[-1]:
                    stack.pop()
                    if len(stack) == 0:
                        stack.append(prices[i])
                        ans[i] = prices[i]
                        break
                else:
                    stack.append(prices[i])
                    ans[i] = stack[0]
                    break
        res = 0
        for a, m in zip(ans, prices):
            res = max(res, a - m)
        return res   

우리는 여전히 이 접근 방식을 최적화할 수 있습니다. 각각의 작은 요소에 대해 오른쪽의 큰 요소에 관심이 있습니다. 따라서 배열을 반복하는 동안 두 가지 가능성에 도달할 수 있습니다.

새 요소가 current_min보다 크며 이 경우 max_profit을 업데이트합니다.

새 요소는 current_min보다 작습니다. 이 경우 current_min을 업데이트합니다.
해결책

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        current_min = float('inf')
        max_profit = 0
        for price in prices:
            if price < current_min:
                current_min = price
            else:
                max_profit = max(max_profit, price - current_min)
        return max_profit

편집하다 -
재미를 좀 보려고 하다가 이 하나의 라이너를 생각해 냈습니다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return reduce(lambda p,c: (max(p[0], c - p[-1]) , min(p[-1], c)) if type(p) == type((1,2,)) else (0, c), [0] + prices)[0] if prices else 0