121.买卖股票的最佳时机 122.买卖股票的最佳时机II
121.买卖股票的最佳时机
力扣题目链接(opens new window)
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
- 示例 1：
- 输入：[7,1,5,3,6,4]
- 输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 - 示例 2：
- 输入：prices = [7,6,4,3,1]
- 输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
思路:贪心
这道题目用贪心可以解决，回顾下贪心算法
需要定义局部最优解和整体最优解
题目只要求买卖一次股票，并获取最大利润
要找到股票左侧最低点，并在右侧最高点卖出
找最低点和最高点的流程可以用一个For循环来解决
遍历数组prices，假设遍历的元素就是右侧最高点，在遍历过的元素中找到最低点，即为左侧最低点
计算利润差值即可
局部最优解：找到当前左侧的最低点，计算当前利润最大值
整体最优解：这笔交易中获取的最大利润
时间复杂度o(n)
空间复杂度o(1)
代码如下
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int low = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
low = Math.min(low, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - low);
}
return maxProfit;
}
思路:动态规划
思路：动态规划 股票类问题，动态规划解法是通用解法 动态规划五部曲 1.dp数组以及下标代表含义 之前做惯了背包类题目，习惯定义一维数组解决问题。不是背包类题目，要根据题意具体分析 定义一维数组dp[i]，表示第i天从这笔交易中获取的最大利润。但买和卖这两种状态无法表示 因此定义二维数组dp[i][j]。j = 0 表示第i天不持有股票利润 j = 1表示第i天持有股票的利润 要用持有和不持有股票作为状态，不用出售和不出售作为状态(因为还要定义【保持卖出状态】和【保持买入状态】） 2.确定递推公式 第i天不持有股票。 1.第i-1天不持有股票 dp[i][0] = dp[i-1][0] 2.第i-1天持有股票 dp[i][0] = prices[i] + dp[i-1][1] dp[i][0] = Math.max(dp[i-1][0],prices[i] + dp[i-1][1]) 第i天持有股票 1.第i-1天不持有股票dp[i][1] = -price[i] 2.第i-1天持有股票dp[i][1] = dp[i-1][1] dp[i][1] = Math.max( -prices[i],dp[i-1][1]) 3.dp数组初始化 dp[0][0] = 0 dp[0][1] = -prices[0] 4.遍历顺序，dp[i]由dp[i-1]推导，故正序 5.举例推导dp数组 时间复杂度o(n) 空间复杂度o(n)
代码如下
public static void main(String[] args) {
int[] prices = new int[]{7, 1, 5, 3, 6, 4};
maxProfit(prices);
}
public static int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
}
return dp[prices.length - 1][0];// 最后一天肯定不持有
}
122.买卖股票的最佳时机II
力扣题目链接(opens new window)
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 - 示例 2:
- 输入: [1,2,3,4,5]
- 输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 - 示例 3:
- 输入: [7,6,4,3,1]
- 输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：文章来源：https://www.toymoban.com/news/detail-796433.html
- 1 <= prices.length <= 3 * 10 ^ 4
- 0 <= prices[i] <= 10 ^ 4
思路
思路：动态规划 思路和买卖股票的最佳时机类似，区别在于递推公式 dp[i][0] j = 0表示未持有,此部分逻辑不变 i- 1 持有股票：dp[i][0] = prices[i] + dp[i-1][1] i- 1 未持有股票：dp[i][0] = dp[i-1][0] dp[i][1] j = 1表示持有。i-1未持有股票逻辑变化 i- 1 持有股票：dp[i][1] = dp[i-1][1] i- 1 未持有股票：dp[i][1] = dp[i-1][0] - prices[i] 变化在此处 因为股票可以买卖多次。当前未持有股票的利润，可能包含之前买卖股票的利润 所以需要用之前买卖股票的利润 - 当前持有股票的利润
代码如下文章来源地址https://www.toymoban.com/news/detail-796433.html
// 时间复杂度o(n)
// 空间复杂度o(n)
public int maxProfitII(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], prices[i] + dp[i - 1][1]);
dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
}
return dp[prices.length - 1][0];// 最后一天肯定不持有
}
到了这里，关于121.买卖股票的最佳时机 122.买卖股票的最佳时机II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
