728x90
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Best Time to Buy and Sell Stock - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
< 내가 만든 시간초과 풀이 >
def maxProfit(self, prices: List[int]) -> int:
ans = 0
tmp =0
for i in range(len(prices)) :
ans = max(tmp,ans)
for j in range(i,len(prices)) :
if prices[i] < prices[j] :
if tmp < (prices[j] - prices[i]) : tmp = prices[j] - prices[i]
return ans문제를 보고 무턱대로 완탐으로 만들었다.
결과는 시간초과ㅎㅎ
파이썬 알고리즘 인터뷰의 2번째 풀이 - 저점과 현재 값과의 차이 계산으로 코드를 만들어보았다.
def maxProfit(self, prices: List[int]) -> int:
profit = 0
min_price = sys.maxsize
for price in prices :
min_price = min(price, min_price)
profit = max(price - min_price, profit)
return profit
저점을 찾아 O(n) 동안 가격차이를 계산하여 가격차이가 가장 큰 값을 반환하도록 만들면
시간초과가 발생하지않는다.
반응형
'프로그래밍 > 프로그래밍책📚' 카테고리의 다른 글
| 면접을 위한 CS전공지식 노트_OS (0) | 2022.06.24 |
|---|---|
| [leetcode][Python]234. Palindrome Linked List(4일간의 팰린드롬 연결리스트 해결기🤪) (0) | 2022.02.04 |
| [리트코드][Python]125-valid Palindrome (0) | 2022.01.25 |
| (2)파이썬알고리즘인터뷰 - leetCode:[819]Most Common Word (0) | 2022.01.22 |
| (1)파이썬알고리즘인터뷰 - 빅오와 자료형 (0) | 2022.01.21 |