121. 买卖股票的最佳时机

题目

给定一个数组 prices ,它的第 i元素 prices[i] 表示一支给定股票i 天的价格。

你只能选择 某一天 买入这只股票,并选择未来的某一个不同的日子 卖出该股票。设计一个算法计算你所能获取最大利润

返回可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0

示例

示例 1:

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

输入prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。 

提示

解题

方法一:一次循环贪心

解题思路

  1. 初始化变量 使用 inf(正无穷大的常量初始minprice表示遍历过程中的最小价格,同时初始maxprofit 为 0,表示卖出股票时的最大利润

  2. 遍历数组 对于每一天的股票价格,进行以下操作

  3. 返回结果 最终返回 maxprofit,即最大利润

这种方法核心思想是,在遍历数组过程中,始终保持 minprice 记录的是当前为止的最小价格,而 maxprofit 记录的是当前为止的最大利润通过不断更新两个变量可以一次遍历找到最佳的买入和卖出时机,从而得到最大利润。

class Solution {
public:
    int maxProfit(vector<int&gt;&amp; prices) {
        int inf = 1e9;          // 用于表示无穷大的常量
        int minprice = inf;      // 记录遍历过程中的最小价格
        int maxprofit = 0;       // 记录卖出股票时的最大利润

        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);  // 更新最大利润
            minprice = min(price, minprice);               // 更新最小价格
        }

        return maxprofit;  // 返回最终的最大利润
    }
};

复杂度分析

原文地址:https://blog.csdn.net/m0_53485135/article/details/134786570

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_44694.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注