领扣-121/122 最佳买卖时机 Best Time to Buy and Sell MD
目录
目录
买卖股票的最佳时机 -121
题目
暴力法
贪心算法(波峰波谷法)
优化
买卖股票的最佳时机 II -122
题目
波峰波谷法
波峰波谷法优化
累加法
买卖股票的最佳时机 III -123
动态规划 二维数组(不懂)
动态规划 一维数组(不懂)
买卖股票的最佳时机 IV -188
动态规划(不懂)
买卖股票的最佳时机 -121
题目
暴力法
贪心算法(波峰波谷法)
优化
买卖股票的最佳时机 II -122
题目
波峰波谷法
波峰波谷法优化
累加法
买卖股票的最佳时机 III -123
动态规划 二维数组(不懂)
动态规划 一维数组(不懂)
买卖股票的最佳时机 IV -188
动态规划(不懂)
买卖股票的最佳时机 -121
数组 贪心算法
题目
给定一个数组，它的第 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;
}
}买卖股票的最佳时机 II -122
数组 贪心算法
题目
给定一个数组，它的第 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;
}
}买卖股票的最佳时机 III -123
给定一个数组，它的第 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];
}
}买卖股票的最佳时机 IV -188
给定一个数组，它的第 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;
}
}2016-12-29
2018-12-16