1.暴力兩層循環(huán),思路沒啥問題,時間LeetCode上會超時
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var maxProfit = 0
for cursor_0 in 0..<prices.count {
for cursor_1 in (cursor_0 + 1)..<prices.count {
if (prices[cursor_1] - prices[cursor_0]) > maxProfit {
maxProfit = prices[cursor_1] - prices[cursor_0]
}
}
}
return maxProfit
}
}
- 換一個思路,每個時間賣出的最大價格都是和前面最小價格的差抄瓦,多用一個變量記錄一下前面的最小值實現(xiàn)復雜度降到O(n)
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
var minPrice = Int.max
var maxProfit = 0
for cursor in 0..<prices.count {
if prices[cursor] < minPrice {
minPrice = prices[cursor]
}else if prices[cursor] - minPrice > maxProfit {
maxProfit = prices[cursor] - minPrice
}
}
return maxProfit
}
}