Best Time to Buy and Sell Stock

Question

题解

最多只允许进行一次交易,显然我们只需要把波谷和波峰分别找出来就好了。但是这样的话问题又来了,有多个波峰和波谷时怎么办?——找出差值最大的一对波谷和波峰。故需要引入一个索引用于记录当前的波谷,结果即为当前索引值减去波谷的值。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
if prices is None or len(prices) <= 1:
return 0

profit = 0
cur_price_min = 2**31 - 1
for price in prices:
profit = max(profit, price - cur_price_min)
cur_price_min = min(cur_price_min, price)

return profit

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
if (prices.size() <= 1) return 0;

int profit = 0;
int cur_price_min = INT_MAX;
for (int i = 0; i < prices.size(); ++i) {
profit = max(profit, prices[i] - cur_price_min);
cur_price_min = min(cur_price_min, prices[i]);
}

return profit;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;

int profit = 0;
int curPriceMin = Integer.MAX_VALUE;
for (int price : prices) {
profit = Math.max(profit, price - curPriceMin);
curPriceMin = Math.min(curPriceMin, price);
}

return profit;
}
}

源码分析

善用maxmin函数,减少if的使用。

复杂度分析

遍历一次 prices 数组,时间复杂度为 $$O(n)$$, 使用了几个额外变量,空间复杂度为 $$O(1)$$.

Reference

  • soulmachine 的卖股票系列



评论

Your browser is out-of-date!

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

×