题解 | JZ63 买卖股票的最好时机(一)
这个题看一眼就会想到是动态规划的解法，但是我们发现它只能买卖一次股票，这个限制条件很强。而且下面也给出了空间复杂度为O(1),也就意味着DP的解法并不是最优的。
所以我们想到一个方法，就是拿后面的最大值，来减去前面的最小值，就可以知道了。
这里面需要注意有一个次序在里面，不是随便找一个最大值和最小值做减法就可以的。所以我们想到从前往后遍历一边，然后拿当前的值减去记录的历史的最小值，就可以发现正确答案了。
class Solution {
public:
/**
*
* @param prices int整型vector
* @return int整型
*/
int maxProfit(vector<int>& prices) {
// write code here
int minn = 10000;
int ans = 0;
for (int i = 0; i < prices.size(); i++) {
minn = min(minn, prices[i]);
ans = max(ans, prices[i] - minn);
}
return ans;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param prices int整型一维数组
# @return int整型
#
class Solution:
def maxProfit(self , prices: List[int]) -> int:
# write code here
minn = 100000
ans = 0
for i in range(len(prices)):
minn = min(minn, prices[i])
ans = max(ans, prices[i] - minn)
return ans
查看16道真题和解析
投递百度等公司10个岗位