LeetCode Digest
1 分鐘 閱讀文 (大約 214 個字)

121. Best Time to Buy and Sell Stock

題目
思路

  1. 最直覺的想法是從頭開始 traverse array，針對每一個 price 都去算一次那個位置之後的所有可能利潤，不過這樣會是兩個巢狀 for-loop，時間複雜度是 O(n^2)，太大了
  2. 有沒有辦法只 traverse 一次 array 就好？
  3. 利潤是由買價和賣價得出，知道最低買價和最高賣價就可以得出答案。有辦法設定這兩個變數，然後隨著 array traversal 不斷更新嗎？
    • 可以把 最高賣價 改成 最大利潤，因為這個才是需回傳的答案
Python 3 solution
1
2
3
4
5
6
7
8
9
def maxProfit(self, prices: List[int]) -> int:
    min_bid = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_bid:
            min_bid = price
        elif price - min_bid > max_profit:
            max_profit = price - min_bid
    return max_profit
#
409. Longest Palindrome
為什麼 Python 的 in 用在 set 是 O(1) 時間複雜度？

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×