目录
刷题日期：下午9:08 2021年5月26日星期三
个人刷题记录，代码收集，来源皆为leetcode
经过多方讨论和请教，现在打算往Java方向发力
主要答题语言为Java
题目：
剑指 Offer 63. 股票的最大利润
难度中等121
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
限制：
0 <= 数组长度 <= 10^5
题目分析
一看限制人就傻了，断了两层遍历的暴力念头。
示例一的解释也云里雾里的，难道不应该是先买入再卖出吗。
从前往后遍历，首先找有没有递增的，有的话把最小的设为买，往后找，不断更新最大的卖点，如果出现了最小的卖点也可以记录，然后取最值。
最大最小还有先后的限制，估计还得整一个数组之类的，因为可能有好几对。
初始解答：
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int in = prices[0], out = prices[0]; //买入和卖出的价格，都初始化最低
for (int i = 0; i < prices.length - 1; i++) {
//如果递减则不做事
if (prices[i] < prices[i + 1] && prices[i] != 0) {
if (prices[i] < in) {
in = prices[i];
}
out = prices[i + 1];
}
if (prices[i] < prices[i + 1] && prices[i] > out) out = prices[i];
}
return out - in;
}
}
执行结果：解答错误
显示详情 添加备注
输入：[2,1,2,1,0,1,2]
输出：1
预期结果：2
我就醉了，前面的0已经判断为闭市不交易了，和着现在，0成了免费送了呗，这啥股市啊，你家开的。
思路还差一点，不过方向是对的，对怎么维护最大利益想的还不够清楚，方法一也采用了类似的做法，稍加修改就好了
class Solution {
public int maxProfit(int[] prices) {
if (prices.length <= 1) return 0;
int in = prices[0], res = 0; //买入的价格初始化
for (int i = 1; i < prices.length; i++) {
//如果递减则不做事
if (prices[i] <= in) {
in = prices[i];
} else {
res = Math.max(res, prices[i] - in);
}
}
return res;
}
}
执行结果：通过
显示详情 添加备注
执行用时：1 ms, 在所有 Java 提交中击败了98.16%的用户
内存消耗：37.9 MB, 在所有 Java 提交中击败了94.30%的用户
再学习K神的做法，采用动态规划
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price : prices) {
cost = Math.min(cost, price); //不断更新最小值，单向遍历保证不会倒
profit = Math.max(profit, price - cost); //不断更新最大利润
}
return profit;
}
}
效果差不多， 执行结果：通过
显示详情 添加备注
执行用时：2 ms, 在所有 Java 提交中击败了66.62%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了59.95%的用户
学习他人：
方法一:
mata川L5 2020-02-13 在遍历数组的过程中，维护一个最小值，最小值初试为prices[0]
- 如果prices[i]大于min，则去更新一下利润res
- 否则说明当前的prices[i]比min还小，则更新min
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length <= 1) {
return 0;
}
int res = 0, min = prices[0];
for(int i = 1; i < prices.length; i++) {
if(prices[i] <= min) {
min = prices[i];
}else {
res = Math.max(res, prices[i] - min);
}
}
return res;
}
}
方法二：
wydxryL1 2021-04-11
执行结果： 通过 显示详情 执行用时： 2 ms , 在所有 Java 提交中击败了 66.06% 的用户 内存消耗： 38.3 MB , 在所有 Java 提交中击败了 52.70% 的用户
class Solution {
public int maxProfit(int[] prices) {
if(prices.length==0) return 0;
int minp=prices[0],maxp=0;
for(int i=1;i<prices.length;i++){
minp=Math.min(minp,prices[i]);
maxp=Math.max(maxp,prices[i]-minp);
}
return maxp;
}
}
方法三：
无敌挂科男L1 4 天前
class Solution {
public int maxProfit(int[] prices) {
//在某天卖出的最大利润依赖于之前的最小价格
//1.遍历一遍，同时更新最低买入价格
if(prices.length < 2)
return 0;
int maxProfit = Integer.MIN_VALUE;
int minPrice = prices[0];
for(int i = 1; i < prices.length; ++i){
//更新最大收益
maxProfit = Math.max(prices[i] - minPrice, maxProfit);
//更新最低买入价格
minPrice = Math.min(prices[i], minPrice);
}
return maxProfit > 0 ? maxProfit : 0;
}
}
方法四：
K神 暴力法的时间复杂度为 O(n^2)。考虑使用动态规划降低时间复杂度，以下按照流程解题。
作者：jyd
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/solution/mian-shi-ti-63-gu-piao-de-zui-da-li-run-dong-tai-2/
来源：力扣（LeetCode）
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}
总结
以上就是本题的内容和学习过程了，重点在于如何更新最低价和最高价，或者聪明点学K神直接更新最大利润，能想出来递推公式是关键。
欢迎讨论，共同进步。