目录
| Markdown版本笔记 | 我的GitHub首页 | 我的博客 | 我的微信 | 我的邮箱 |
|---|---|---|---|---|
| bqt20094 | baiqiantao@sina.com |
领扣-121/122 最佳买卖时机 Best Time to Buy and Sell MD
*** 目录 ===数组 贪心算法
题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天的时候买入，在第 5 天的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
方法声明：
class Solution { public int maxProfit(int[] prices) { }} 暴力法
class Solution { public int maxProfit(int[] prices) { int max = 0; for (int i = 0; i < prices.length; i++) { for (int j = i + 1; j < prices.length; j++) { max = Math.max(max, prices[j] - prices[i]); } } return max; }} 时间复杂度：O(n^2)
O(1) 贪心算法(波峰波谷法)
对于这道题，我们很明显能感觉到，不是单纯的找出数组中的最小值和最大值，然后求他们的差的，因为最小值不一定在最大值的前面。
但是也很明显，这道题确实是让我们找最值的，问题出在哪呢？
问题出在，这道题其实是让我们求极小值和极大值的，也即先找出一个波段内的极小值和极大值，然后如果发现另一个更小的极小值后，再找出从此极小值开始后的极大值；最终我们比较的是这些极大值和极小值的差中的最大值。
class Solution { public int maxProfit(int[] prices) { int maxprofit = 0, temMax = 0, minprice = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++) { if (prices[i] < minprice) { //一旦找到更小的值，则开始从此点找极大值 minprice = prices[i]; //始终存的的是已发现的最小值 temMax = 0;//重新开始计算差值(这一步是可以忽略的) } else { temMax = prices[i] - minprice; maxprofit = Math.max(maxprofit, temMax);//和之前的最大利润做比较 } } return maxprofit; }} 优化
以上逻辑等价于如下形式：
class Solution { public int maxProfit(int[] prices) { int maxprofit = 0, minprice = Integer.MAX_VALUE; for (int price : prices) { if (price < minprice) { //一旦找到更小的值，则开始从此点找极大值 minprice = price; //始终存的的是已发现的最小值 } else { maxprofit = Math.max(maxprofit, price - minprice);//和之前的最大利润做比较 } } return maxprofit; }} 也等价于如下形式，虽然这种形式代码量小了一些，但这种形式其实计算多个很多：
class Solution { public int maxProfit(int[] prices) { int maxprofit = 0, buy = Integer.MAX_VALUE; for (int price : prices) { buy = Math.min(buy, price); maxprofit = Math.max(maxprofit, price - buy); } return maxprofit; }} 数组 贪心算法
题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
波峰波谷法
class Solution { public int maxProfit(int[] prices) { int maxprofit = 0, minprice = Integer.MAX_VALUE, maxprice = Integer.MAX_VALUE; boolean findMin = true; //找波谷还是波峰 for (int i = 0; i < prices.length; i++) { if (findMin) { //找波谷 if (prices[i] < minprice) { //有更低的波谷 minprice = prices[i]; //更新购买价格 maxprice = prices[i]; } else { //比波谷的值大，那么我们就找波峰 maxprice = prices[i]; //更新卖出价格 findMin = false; } } else { //找波峰 if (prices[i] > maxprice) { //有更高的波峰 maxprice = prices[i]; //更新卖出价格 } else { //比波峰小，那么我们就在之前卖出，然后在这里买入 maxprofit += (maxprice - minprice); //更新收益 minprice = prices[i]; //重置所有状态 maxprice = prices[i]; findMin = true; } } } return maxprofit + (maxprice - minprice);//防止最后在找波峰过程中结束，导致没有卖出的问题 }} 时间复杂度：O(n)
O(1) 波峰波谷法优化
上面的代码实际上有很多运算时可以忽略的，可以优化为如下逻辑
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; int i = 0, valley = prices[0], peak = prices[0], maxprofit = 0; while (i < prices.length - 1) { while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++; //有更低的波谷 valley = prices[i]; //更新购买价格 while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++; //有更高的波峰 peak = prices[i]; //更新卖出价格 maxprofit += peak - valley; } return maxprofit; }} 累加法
我们不需要跟踪峰值和谷值对应的成本以及最大利润，我们可以直接继续增加数组的连续数字之间的差值，如果第二个数字大于第一个数字，我们获得的总和将是最大利润。这种方法将简化解决方案。
例如：[1, 7, 2, 3, 6, 7, 6, 7]
与此数组对应的图形是：
从上图中，我们可以观察到 A+B+C 的和等于差值 D 所对应的连续峰和谷的高度之差。
class Solution { public int maxProfit(int[] prices) { int maxprofit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) maxprofit += prices[i] - prices[i - 1]; } return maxprofit; }} 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 动态规划 二维数组(不懂)
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; int n = prices.length; int[][] g = new int[n][3], l = new int[n][3]; for (int i = 1; i < n; i++) { int diff = prices[i] - prices[i - 1]; for (int j = 1; j <= 2; j++) { l[i][j] = Math.max(g[i - 1][j - 1] + Math.max(diff, 0), l[i - 1][j] + diff); g[i][j] = Math.max(l[i][j], g[i - 1][j]); } } return g[n - 1][2]; }} 动态规划 一维数组(不懂)
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; int n = prices.length; int[] g = new int[3], l = new int[3]; for (int i = 0; i < n - 1; i++) { int diff = prices[i+1] - prices[i ]; for (int j = 2; j >= 1; j--) { l[j] = Math.max(g[j - 1] + Math.max(diff, 0), l[j] + diff); g[j] = Math.max(l[j], g[j]); } } return g[2]; }} 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 方法声明
class Solution { public int maxProfit(int k, int[] prices) { }} 动态规划(不懂)
class Solution { public int maxProfit(int k, int[] prices) { if (prices == null || prices.length <= 1) return 0; int n = prices.length; if (k >= n) return maxProfit(prices); int[] g = new int[k + 1], l = new int[k + 1]; for (int i = 0; i < n - 1; i++) { int diff = prices[i + 1] - prices[i]; for (int j = k; j >= 1; j--) { l[j] = Math.max(g[j - 1] + Math.max(diff, 0), l[j] + diff); g[j] = Math.max(l[j], g[j]); } } return g[k]; } public int maxProfit(int[] prices) { int maxprofit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) maxprofit += prices[i] - prices[i - 1]; } return maxprofit; }} 2018-12-16