【leetcode刷题】T14-买卖股票的最佳时机 II
这是木又陪伴你的第22天
今天分享leetcode第14篇文章，也是leetcode第122题—买卖股票的最佳时机
【英文题目】（学习英语的同时，更能理解题意哟~）
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.【中文题目】
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 :
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。【思路】
本题与「T13-买卖股票的最佳时机」最大的区别是可以买卖多次，那么每次在局部最低点购买，在局部最高点卖出，就能获取最大利润。
那么怎么寻找局部最高点和局部最低点呢？当今天价格小于昨天价格时，今天价格就是局部最低点，昨天价格就是局部最高点，就应该昨天卖出，今天买入。有个问题，明天价格小于今天价格怎么办？一样的，明天买入，今天卖出。那么今天一个买入，一个卖出，相当于不交易。这个解法需要注意最后一天的处理！
还有一种解法，可以称之为“累加法”：只要今天价格大于昨天价格，就可以理解为昨天买入，今天卖出，直接赚取利润。同时明天价格更高的话，今天买入，明天卖出，相当于今天不进行交易。但是利润相当于明天价格-昨天价格。
【代码】
python版本
局部最高-局部最低
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
i = 1
length = len(prices)
if length < 2:
return 0
# 局部最高-局部最低
min0 = prices[0]
res = 0
while i < length:
if prices[i] < prices[i-1]:
res += prices[i-1] - min0
min0 = prices[i]
i += 1
# 最后一个元素未处理
res += prices[-1] - min0
return res累加
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
res = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
res += prices[i] - prices[i-1]
return resC++版本
局部最高-局部最低
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2)
return 0;
int res = 0;
int min = prices[0];
for(int i=1; i<prices.size(); i++){
// 局部高价卖出
if(prices[i] < prices[i-1]){
res += prices[i-1] - min;
min = prices[i];
}
}
res += prices[prices.size()-1] - min;
return res;
}
};累加
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i=1; i<prices.size(); i++){
// 昨天买，今天卖
if(prices[i] > prices[i-1])
res += prices[i] - prices[i-1];
}
return res;
}
};这告诉了我们，股票要低买高卖~