部队网站设计,做视频网站空间要多大,个体户怎么注册商标,详情页模板怎么做121.买卖股票的最佳时机 122.买卖股票的最佳时机II
121.买卖股票的最佳时机
力扣题目链接(opens new window)
给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一…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。
提示
1 prices.length 3 * 10 ^ 40 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] 变化在此处
因为股票可以买卖多次。当前未持有股票的利润可能包含之前买卖股票的利润
所以需要用之前买卖股票的利润 - 当前持有股票的利润代码如下
// 时间复杂度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];// 最后一天肯定不持有
}
