普通暴力解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } int ans = 0; for (int i = 0; i < prices.length - 1; i++) { for (int j = i + 1; j < prices.length; j++) { if (prices[j] > prices[i]) { ans = Math.max(ans, prices[j] - prices[i]); } } } return ans;}
暴力递归解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } return process(prices, 0, -1, -1);}public int process(int[] prices, int i, int buyDay, int sellDay) { if (prices.length == i) { if (buyDay > -1 && buyDay < sellDay && prices[buyDay] < prices[sellDay]) { return prices[sellDay] - prices[buyDay]; } return 0; } // 在第i天不操作 int p0 = process(prices, i + 1, buyDay, sellDay); // 在第i天买入 int p1 = 0; if (buyDay == -1 && sellDay == -1) { p1 = process(prices, i + 1, i, sellDay); } // 在第i天卖出 int p2 = 0; if (buyDay > -1 && sellDay == -1) { p2 = prices[i] > prices[buyDay] ? prices[i] - prices[buyDay] : 0; } return Math.max(p0, Math.max(p1, p2));}
另一种暴力递归可推导出动态规划:
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } return process(prices, 0, 0);}public int process(int[] prices, int i, int flag) { // base case if (i == 0) { if (flag == 0) { return 0; } return -prices[0]; } if (flag == 0) { // 第i天不持有股票 return Math.max(process(prices, i - 1, 1) + prices[i], process(prices, i - 1, 0)); } else { return Math.max(process(prices, i - 1, 1), -prices[i]); }}
动态规划解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } int len = prices.length; // dp[i][0] 下标为 i 这天结束的时候,不持股,手上拥有的现金数 // dp[i][1] 下标为 i 这天结束的时候,持股,手上拥有的现金数 int[][] dp = new int[len][2]; // 初始化:不持股显然为 0,持股就需要减去第 1 天(下标为 0)的股价 dp[0][0] = 0; dp[0][1] = -prices[0]; // 从第 2 天开始遍历 for (int i = 1; i < len; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); } return dp[len - 1][0];}
在暴力递归的基础上加缓存,转变成记忆化搜索:
最终版的动态规划是怎么写出来的呢?请看下图:
单调栈解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } int ans = 0; //int min = 0; //Stack<Integer> upStack = new Stack<Integer>(); int topIndex = -1; // 记录栈顶下标 int[] upStack = new int[prices.length]; for (int i = 0; i < prices.length; i++) { // 由小到大的单调栈 //while (!upStack.empty() && upStack.peek() > prices[i]) { while (topIndex > -1 && upStack[topIndex] > prices[i]) { //int p = upStack.pop(); int p = upStack[topIndex--]; int min = upStack[0]; if (p > min) { ans = Math.max(ans, p - min); } } /*if (upStack.empty()) { min = prices[i]; }*/ //upStack.push(prices[i]); upStack[++topIndex] = prices[i]; } // 栈顶元素未被处理 //if (upStack.size() > 1) { if (topIndex > 0) { //int p = upStack.pop(); int p = upStack[topIndex--]; int min = upStack[0]; if (p > min) { ans = Math.max(ans, p - min); } } return ans;}
直接使用 java.util.Stack 会对性能会造成影响,因此这里利用数组来优化。
滑动窗口解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } // minWindow 由小到大 LinkedList<Integer> minWindow = new LinkedList<Integer>(); for (int R = 0; R < prices.length; R++) { while (!minWindow.isEmpty() && prices[minWindow.peekLast()] >= prices[R]) { minWindow.pollLast(); } minWindow.addLast(R); int buyPrice = prices[minWindow.peekFirst()]; int sellPrice = prices[R]; if (sellPrice > buyPrice) { ans = Math.max(ans, sellPrice - buyPrice); } } return ans;}
线段树解
public int maxProfit(int... prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0] >= prices[1])) { return 0; } int ans = 0; SegmentTree segmentTree = new SegmentTree(prices); for (int i = 0; i < prices.length; ++i) { int buyPrice = prices[i]; int sellPrice = segmentTree.query(i + 1, prices.length, 1, prices.length, 1); ans = Math.max(ans, sellPrice - buyPrice); } return ans;}public class SegmentTree { private int[] data; private int[] max; public SegmentTree(int[] src) { int N = src.length + 1; data = src; max = new int[N << 2]; build(1, N - 1, 1); } private void pushUp(int i) { max[i] = Math.max(max[i << 1], max[i << 1 | 1]); } private void pushDown(int i) { } private void build(int l, int r, int i) { if (l == r) { max[i] = data[l - 1]; return; } int mid = (l + r) >> 1; build(l, mid, i << 1); build(mid + 1, r, i << 1 | 1); pushUp(i); } public int query(int L, int R, int l, int r, int i) { if (L <= l && r <= R) { return max[i]; } int mid = (l + r) >> 1; pushDown(i); int left = 0; int right = 0; if (L <= mid) { left = query(L, R, l, mid, i << 1); } if (R > mid) { right = query(L, R, mid + 1, r, i << 1 | 1); } return Math.max(left, right); }}
树状数组解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } int ans = 0; IndexTree indexTree = new IndexTree(prices.length); for (int i = 0; i < prices.length; i++) { indexTree.set(i + 1, prices[i]); } for (int i = 1; i < prices.length; i++) { int min = indexTree.min(i + 1); if (prices[i] > min) { ans = Math.max(ans, prices[i] - min); } } return ans;}public static class IndexTree { private int[] tree; private int N; // 0位置弃而不用 public IndexTree(int size) { N = size; tree = new int[N + 1]; for (int i = 1; i <= N; i++) { tree[i] = Integer.MAX_VALUE; } } // 返回 [1, index] 范围最小值 public int min(int index) { int ret = Integer.MAX_VALUE; while (index > 0) { ret = Math.min(tree[index], ret); index -= index & -index; } return ret; } // index & -index : 提取出index最右侧的1出来 // 假设 index 为 : 0011001000 // index & -index : 0000001000 public void set(int index, int v) { while (index <= N) { tree[index] = Math.min(tree[index], v); index += index & -index; } }}
最优解
public int maxProfit(int[] prices) { if (null == prices || prices.length < 2 || (prices.length == 2 && prices[0]>=prices[1])) { return 0; } int ans = 0; int minPre = prices[0]; for (int i = 1; i < prices.length; i++) { if (prices[i] > minPre) { ans = Math.max(ans, prices[i] - minPre); } else { minPre = prices[i]; } } return ans;}
以上花式炫技,你学废了吗?
相关内容
MilkyWay将向mPoint持有者空
以太坊L2网络MintBlockchai
做市商GSRMarkets和Winter
AI教父GeoffreyHinton建议
BitMEX创始人一小时前从Winter
BeosinTraceDMM被盗资金已被
数据ArthurHayes于1小时前从W
WintermuteCEO以太坊领导者陷
FranklinTempletonCEO
Franklin数字资产主管美SEC今年
文章来源:
财源网
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 931614094@qq.com 举报,一经查实,本站将立刻删除。