1.买卖股票的最佳时机
使用双指针
i尝试买入，j尝试卖出
遇到涨i不变，j++
遇到跌i变j，j++
package com.dreams.leetcode;
public class Leetcode121 {
static int maxProfit(int[] prices) {
int i = 0;
int j = 1;
int max = 0;
while (j < prices.length) {
if (prices[j] - prices[i] > 0) { // 涨
max = Math.max(max, prices[j] - prices[i]);
j++;
} else { // 跌
i = j;
j++;
}
}
return max;
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4})); // 5
System.out.println(maxProfit(new int[]{9, 3, 12, 1, 2, 3})); // 9
}
}
2.买卖股票的最佳时机 II
贪心思想：
- 初始化两个指针 i 和 j，分别表示买入点和卖出点，初始时分别指向第一天和第二天的价格。
- 在一个循环中，不断比较相邻两天的股票价格，并计算利润。
- 如果当天价格高于前一天，即价格上涨，就计算利润并累加到总利润中。
- 更新买入点和卖出点，继续向后遍历。
- 最终返回累计的利润。
代码：
package com.dreams.leetcode;
public class Leetcode122 {
static int maxProfit(int[] prices) {
int i = 0;
int j = 1;
int sum = 0;
while (j < prices.length) {
if (prices[j] - prices[i] > 0) { // 有利润
sum += prices[j] - prices[i];
}
i++;
j++;
}
return sum;
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{9, 3, 12, 1, 2, 3})); // 11
System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4})); // 7
}
}
3.买卖股票的最佳时机含手续费
存在手续费就不能使用贪心算法了
这里使用动态规划
对于买的选择：
- 延续上次买的利润不变
- 在上次卖的利润基础上买
对于卖的选择：
- 延续上次卖的利润不变
- 在上次买的利润基础上卖
代码：
package com.dreams.leetcode;
public class Leetcode714 {
static int maxProfit(int[] prices, int fee) {
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
sell[0] = 0;
for (int i = 1; i < prices.length; i++) {
buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i] - fee);
}
return sell[prices.length - 1];
}
public static void main(String[] args) {
// 两次交易的情况
System.out.println(maxProfit(new int[]{1, 3, 2, 8, 4, 9}, 2)); // 8
System.out.println(maxProfit(new int[]{1, 3, 7, 2, 18, 3}, 3)); // 16
System.out.println(maxProfit(new int[]{2, 1, 4, 4, 2, 3, 2, 5, 1, 2}, 1)); // 4
System.out.println(maxProfit(new int[]{9, 3, 12, 1, 2, 3}, 1)); // 9
// 一次交易的情况
System.out.println(maxProfit(new int[]{1, 3, 7, 5, 10, 3}, 3)); // 6
System.out.println(maxProfit(new int[]{1, 3, 7, 5, 10, 11, 3}, 3)); // 7
}
}
可以看到实际只用到上一个状态，可以优化为一个变量存储
// 根据上次 buy 计算 sell
static int maxProfit1(int[] prices, int fee) {
int _buy = -prices[0];
int _sell = 0;
for (int i = 1; i < prices.length; i++) {
int buy = Math.max(_buy, _sell - prices[i]);
int sell = Math.max(_sell, _buy + prices[i] - fee);
_buy = buy;
_sell = sell;
}
return _sell;
}
还有一种优化
// 这种改动虽然业务含义变化了，但对结果不影响, 根据这次 buy 计算 sell
static int maxProfit0(int[] prices, int fee) {
int buy = -prices[0];
int sell = 0;
for (int i = 1; i < prices.length; i++) {
buy = Math.max(buy, sell - prices[i]);
sell = Math.max(sell, buy + prices[i] - fee);
}
return sell;
}
4.买卖股票的最佳时机含冷冻期
代码：
package com.dreams.leetcode;
public class Leetcode309 {
static int maxProfit(int[] prices) {
if (prices.length == 1) {
return 0;
}
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
sell[0] = 0;
buy[1] = Math.max(-prices[0], -prices[1]);
sell[1] = Math.max(sell[0], buy[0] + prices[1]);
for (int i = 2; i < prices.length; i++) {
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
}
return sell[prices.length - 1];
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{1, 2, 3, 0, 2})); // 3
}
}
5.买卖股票的最佳时机 III
第一次买 不依赖之前状态，以当日价格买入
第一次卖，依赖于昨天第一次买 + 当日价格
第二次买，依赖于昨天第一次卖 – 当日价格
第二次卖，依赖于昨天第二次买 + 当日价格
package com.dreams.leetcode;
public class Leetcode123 {
static int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE;
int sell1 = 0;
int buy2 = Integer.MIN_VALUE;
int sell2 = 0;
for (int price : prices) {
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1, buy1 + price);
buy2 = Math.max(buy2, sell1 - price);
sell2 = Math.max(sell2, buy2 + price);
}
return sell2;
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{3, 3, 5, 0, 0, 3, 1, 4})); // 6
}
}
6.买卖股票的最佳时机 IV
逻辑：
第一次买 不依赖之前状态，以当日价格买入
第一次卖，依赖于昨天第一次买 + 当日价格
第二次买，依赖于昨天第一次卖 – 当日价格
第二次卖，依赖于昨天第二次买 + 当日价格
第三次买，依赖于昨天第二次卖 – 当日价格
第三次卖，依赖于昨天第三次买 + 当日价格
…
第 k 次买，依赖于昨天第 k-1 次卖 – 当日价格
第 k 次卖，依赖于昨天第 k 次买 + 当日价格
同时如果k的数目已经大于天数大小的1/2，就使用用于计算不限制交易次数时可以获取的最大利润，其采用了简单的贪心算法，效率会高点。
代码：
package com.dreams.leetcode;
import java.util.Arrays;
public class Leetcode188 {
static int maxProfit(int[] prices) {
int i = 0;
int j = 1;
int sum = 0;
while (j < prices.length) {
if (prices[j] - prices[i] > 0) { // 有利润
sum += prices[j] - prices[i];
}
i++;
j++;
}
return sum;
}
static int maxProfit(int k, int[] prices) {
if (k > prices.length / 2) {
return maxProfit(prices);
}
int[] buy = new int[k];
int[] sell = new int[k];
Arrays.fill(buy, Integer.MIN_VALUE);
for (int price : prices) {
buy[0] = Math.max(buy[0], -price);
sell[0] = Math.max(sell[0], buy[0] + price);
for (int i = 1; i < k; i++) {
buy[i] = Math.max(buy[i], sell[i - 1] - price);
sell[i] = Math.max(sell[i], buy[i] + price);
}
}
return sell[k - 1];
}
public static void main(String[] args) {
System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3})); // 7
System.out.println(maxProfit(2, new int[]{3, 3, 5, 0, 0, 3, 1, 4})); // 6
System.out.println(maxProfit(4, new int[]{1, 2, 0, 1, 0, 3, 1, 4, 5})); // 9
}
}
参考
