贪心---买卖股票的最佳时机 Posted on 2021-08-08 00:00:00 2021-08-08 00:00:00 by Author 摘要 买股票了，你能用你的聪明才智赚取更多的利润吗？，想的话就进来瞅瞅吧!!!! # 买卖股票的最佳时机 1. 题目描述 - 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 - **提示：** - `1 <= prices.length <= 105` - `0 <= prices[i] <= 104` 2. 示例描述 - 示例一 ```java 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 ``` 示例二 ```java 输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 ``` 3. 解题思路 - 首先拿到题，分析可知在某一天买入股票，然后在买入股票后的某一天在卖出股票，使得赚到的钱最多。其实可以拿暴力解法去解决。暴力解法思路是在某一天时，我们可以找到某天钱股票最低的时候，那么此时的差值就是在该天能赚取的最大值，然后每天都这样算，找出其中赚取的最大值即可。但是这样时间复杂度为O(N^2)，在leetcode上提交会导致时间超出限制。 - 第二种思路就是贪心解法。这种解法的思路就是当天的股票价格与之前最低的股票相比，如果当天的股票价格低于之前最低的股票价格，那么该天我们可以认为可以购买股票。但是如果当前股票比之前最低的股票价格高，不管高多少，我们可以考虑当天卖出这支股票，那么到底卖不卖这支股票，如果卖出的钱比之前卖出的钱高，那么这次就赚的更多，那么这次就可以卖了，然后记录在此之前赚的最大值，同时在此之前股票最低值也记得了。那么直到最后一天就能找到赚取最大的利润了。 - 以下代码是用贪心算法实现的，暴力解法的思想挺简单，可以自己动手实现的。 4. 代码示例 ```java public int maxProfit(int[] prices) { //最终结果 int result =0; //定义一个当天前股票最低的变量 int min=Integer.MAX_VALUE; for (int i = 0; i <prices.length ; i++) { //如果当天的股票值比之前最低的股票值低，那么就可以在当天买入股票 if(prices[i]<min){ min=prices[i]; } else{ //当天股票比之前最低股票要高，但是我们不知道高多少， //就可以比较当前的股票与之前最低股票差是多少，然后与之前已经赚的股票前相比 //寻找两者间的最大值，一遍能够赚到最多。 result = Math.min(prices[i]-min,result); } } //返回最后结果 return result; } ```
{{ item.content }}
{{ child.content }}