力扣 初级算法 全套力扣精解

初级算法-数组-买卖股票的最佳时机

2021-07-27  本文已影响0人  coenen
给定一个数组 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。
提示:
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
条件分析:
  1. 给一个数组,数据是每天的股票价格 -> 提前知道股票所有价格
  2. 多次买卖同一只股票 -> 手里只能有一只股票
  3. 不能同时参与多笔交易 -> 买了必须卖出,卖出后才能买.不能有留存
  4. 提示说明不是大量数据 -> 说明数据量用的
解决思路1:
  1. 根据条件1,说明我们已经提前知道了股票的涨跌,即涨势图已知
  2. 根据条件2、3,说明只能全买或者全卖
根据涨势我们可以确认是否盈利,根据前一天的价格,如果当天盈利,就相当于卖出,如果不盈利,就买入.如图示:
1.png

如果比前一天是涨的,我就认为我持有这部分收益,如果是持续跌的,我就不买入,坚守股市的低买高卖即可方便理解.当作自己就是巴菲特,能最低买最高卖.
所以只需要与前一天比较即可.如果是涨,就收益.这样就达到最大收益.
代码实现-Swift版本:

思路1代码:

func maxProfit(_ prices: [Int]) -> Int {
        if prices.count < 2 {
            return 0;
        }
        var max = 0
        for i in 0 ..< prices.count - 1 {
            if prices[i] < prices[i + 1] {
                max = max + prices[i + 1] - prices[i]
            }
        }
        
        return max
    }
思路1 提交结果.png

测试用例:

// 只有一个元素
let nums0: [Int] = [3]
// 只有两个相同元素
let nums1: [Int] = [1,1]
// 只有两个不相同元素
let nums2: [Int] = [1,3]
// 先涨
let nums3: [Int] = [1,5,7,8,4,2,7,10,9,3]
// 先跌
let nums4: [Int] = [8,5,2,3,4,6,10,8,19,9]
// 全跌
let nums5: [Int] = [31,25,20,18,14,9,6,3,2,1]
// 全涨
let nums6: [Int] = [1,2,3,4,5,6,7,8,9,15]

考察要点:

上一篇下一篇

猜你喜欢

热点阅读