LeetCode 121. 买卖股票的最佳时机

文章目录

• 前言
• 题目
• 题解
• NO1：一次遍历
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：121. 买卖股票的最佳时机，难度：简单。

题目描述(摘自leetcode)：

给定一个数组 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 <= prices.length <= 105
0 <= prices[i] <= 104

---

题解

NO1：一次遍历

思路：不断的寻找最低点，接着之后若不是最低点则计算当天卖出得到的利润，再去判断利润是否为最大。

代码：时间复杂度O(n)、空间复杂度O(1)

class Solution {
    public int maxProfit(int[] prices) {
        //遍历的过程中不断取得最新的最低点，若不是最低点看一下当天卖出的价格是否为最大值
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++){
            //若是当天为最低价，临时进行保存
            if (prices[i] < minPrice){
                minPrice = prices[i];
            }else if(prices[i] - minPrice > maxProfit){ //当前如果不是最低价，那么来计算出当天卖出时的价格并且与现如今最大利润比较
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }
}

---

参考文章

[1]. leetcode题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.11