1.1. 题目
1.1.1. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 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。
1.1.2. 题解:
- 股票只能买卖一次
- 股票肯定都是正数(其实不影响结果)
- 最后一天买进 是卖不了的
1.1.3. 思路:
- 暴力解法
- 循环以当前天买进,假设后面每天都卖出,与买进的当天相比,谁最大,那么就是最挣钱的
- 动态规划
- 我做动态规划的第三题,终于能自己想出来了..
- 还是循环,以当天的价格为卖出的价格,比如当天是例子里(7,1,5,3,6,4)第三天5,说明以5卖出的话,前面两天里,哪天价格最低,就哪天买进
- 定义一个max表示挣得最大的利润,定义一个整数low表示当天为止的(当天和当天之前的所以天里)最小值
- 以例子举例
7,1,5,3,6,4 - 第一天 low = 7
- 第二天, 第二天的值是 1,但是之前天里 最小价格是low = 7,说明今天比之前价格都低,那么low = prices[1] = 1
- 第三天, 第三天的值是 5,之前最小值是low = 1,比今天的价格底,说明之前1的时候买今天卖肯定挣钱,挣钱数 prices[2] - low 如果比max大,那么将结果赋值给max
- 第四天 ....
- 一直到结束! low 是当天之前存的最小数,
1.1.4. 代码:
点击显示
func maxProfit(prices []int) int {
priceLen := len(prices)
if priceLen <= 1 {
return 0
}
var max int
// 定一个最小值,默认是第一个数
low := prices[0]
for i:=1;i<priceLen;i++ {
//// 如果当前的值 比 之前值的最小值要大,那说明 股票在涨,假设当前卖
if low < prices[i] {
// 如果卖的价格大于之前最大的,那么当前是最挣钱的
if max < prices[i] - low {
max = prices[i] - low
}
} else {
// 说明当前的值比之前的任何一个值都要小,那么存一下当前最小值就是自己本身
low = prices[i]
}
}
return max
}
// 暴力解决
func maxProfit2(prices []int) int {
var max int
priceLen := len(prices)
// 循环到倒数第二个,因为最后一个买进没用,因为无法卖
for i:=0;i<priceLen-1;i++ {
for j:=i+1;j<priceLen;j++ {
// 当是第一个值的时候,默认最大值就是第一天买 第二天卖
if i == 0 && j == 1 {
max = prices[1] - prices[0]
continue
}
// 如果 挣钱最多比 当前股票价格 - 买入的价格之差进行比较,如果差比较大,那么max就是差
if max < prices[j] - prices[i]{
max = prices[j] - prices[i]
}
}
}
// 如果 max小于零,说明就第一次默认的那个卖了,后面都不挣钱,所以都不挣钱,默认为0
if max < 0 {
return 0
}
return max
}