云网站 深圳,51网站空间相册在哪里,东莞电商建站,汕头网站上排名题目描述 给定一个数组 prices#xff0c;其中 prices[i] 表示第 i 天的股票价格。假设你可以在第 i 天买入并在第 j 天卖出股票#xff08;i ≤ j#xff09;#xff0c;设计一个算法来计算你所能获取的最大利润。注意你只能持有一股股票#xff0c;并且你不能同时参与多…题目描述 给定一个数组 prices其中 prices[i] 表示第 i 天的股票价格。假设你可以在第 i 天买入并在第 j 天卖出股票i ≤ j设计一个算法来计算你所能获取的最大利润。注意你只能持有一股股票并且你不能同时参与多笔交易即在再次买入前必须卖出股票。 示例
示例 1:
输入: prices [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出可以获得最大利润为 5。示例 2:
输入: prices [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。题解
这个问题可以通过一次遍历来解决。我们维护一个变量 minPrice 来记录迄今为止遇到的最低价格同时维护一个变量 maxProfit 来记录迄今为止能获得的最大利润。
初始化minPrice 设置为第一个股票价格maxProfit 设置为 0。遍历数组从第二个价格开始遍历股票价格数组。 ○ 对于每个价格如果它小于 minPrice则更新 minPrice。 ○ 否则计算当前利润当前价格减去 minPrice如果这个利润大于 maxProfit则更新 maxProfit。返回结果遍历结束后maxProfit 就是能获得的最大利润。
代码实现
int maxProfit(vectorint prices) {if (prices.empty()) return 0;int minPrice prices[0];int maxProfit 0;for (int i 1; i prices.size(); i) {if (prices[i] minPrice) {minPrice prices[i];} else {int profit prices[i] - minPrice;if (profit maxProfit) {maxProfit profit;}}}return maxProfit;
}复杂度分析
● 时间复杂度O(n)其中 n 是数组 prices 的长度。我们只需要遍历一次数组。 ● 空间复杂度O(1)因为我们只使用了常数个额外变量。 这个算法的优势在于它的时间效率较高只需要一次遍历即可找到最大利润且不需要额外的存储空间。
