目录博客主页：https://tomcat.blog.csdn.net
博主昵称：农民工老王
主要领域：Java、Linux、K8S
期待大家的关注点赞收藏⭐留言
> 创作申明
本文是一篇针对leetcode算法题的解题博客。我给出的解题思路和代码，以及对优质解答的讲解 均属于原创内容，本文的原创标识也是基于此。而题目全部出自leetcode.cn，优质解答搜索自全网，本文已经标明其引用出处。我是一个算法初学者，完全的菜鸟，文中的算法题属于入门级别。本文适合算法新手阅读，而对算法大佬没有任何阅读价值。
- 题目
- 题干
- 示例 1
- 示例 2
- 示例 3
- 我的解答
- 优质解答
题目链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2zsx1/
题干给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2zsx1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
我用Java语言完成解答，解题思路有参考之前的 leetcode初级算法题–原地删除排序数组中的重复项 ，分析在代码注释中：
int result = 0;
//边界判定
if (prices == null || prices.length == 0) {
return result;
}
//双指针：购买 和 卖出
int buy = 0;
int sell = 1;
//循环条件开始设置为(buy < prices.length-1)，也通过了测试，但在写博客时，还觉得应该以sell作为依据，修改后也通过了测试。
while (sell < prices.length) {
//如果明天比今天价高，则有盈利，进入分支进行计算：
if (prices[buy] < prices[sell] ) {
//如果明天是最后一天，或者后天又跌了，就判断应该在明天卖出
if (sell==prices.length-1||prices[sell] > prices[sell + 1]) {
//计算利润
result = result + prices[sell] - prices[buy];
//设置下一个买入日
buy = sell + 1;
//设置下一个卖出日
sell = sell + 2;
}else {
//如果后天继续涨价，则明天不卖出，并将后天设置为 卖出日
sell++;
}
//如果明天价格比今天低，那么设置后天为购买日，后天次日为卖出日
} else {
buy++;
sell=buy+1;
}
}
return result;
通过了leetcode的检测。感觉时间复杂度还将就。
leetcode网页中，题目下面的第一条讨论（作者力扣id：数据结构和算法）中提到的答案就非常优质，获得了很多人的点赞和认同。
他提到了两种方法：动态规划解决和贪心算法。我们这里只介绍贪心算法的解法，这也是最优质的，比较易懂的一个。
先介绍下什么是贪心算法：
以下内容参考自文献 ：谢翌, 江渝川. 大学计算机：计算思维与应用[M]. 1. 重庆: 重庆大学出版社, 2017 :59.
贪心算法一般按如下步骤进行： 建立数学模型来描述问题 → 把求解的问题分成若干个子问题 → 对每个子问题求解，得到子问题的局部最优解 → 把子问题的解局部最优解合成原来解问题的一个解 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。
大佬的代码如下，他的注释已经写得非常清楚了，我就不画蛇添足了：
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int total = 0, index = 0, length = prices.length;
while (index < length) {
//如果股票下跌就一直找，直到找到股票开始上涨为止
while (index < length - 1 && prices[index] >= prices[index + 1])
index++;
//股票上涨开始的值，也就是这段时间上涨的最小值
int min = prices[index];
//一直找到股票上涨的最大值为止
while (index < length - 1 && prices[index] <= prices[index + 1])
index++;
//计算这段上涨时间的差值，然后累加
total += prices[index++] - min;
}
return total;
}
我运行了大佬的代码，leetcode的测评数据的确比我的要好一些。
我对自己的本次解答还是比较满意，总体上来看，算法的时间复杂度，还是和大佬的处于同一个数量级都是O(n)。
但大佬的回答明显更有章法，有成熟的理论，而我只会针对题目中的具体问题进行解答。所以我的解答还是比较低级。此刻我只想对自己说：“老王，这就是差距啊，你要知耻啊！”
如需转载，请注明本文的出处：农民工老王的CSDN博客https://blog.csdn.net/monarch91 。
