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
}

代码

results matching ""

    No results matching ""