剑指offer-75、买卖股票的最好时机
<h2 id="题描述">题⽬描述</h2><p>假设你有⼀个数组 prices ，⻓度为 n ，其中 prices 是股票在第 i 天的价格，请根据这个价格数组，返回买卖股票能获得的最⼤收益</p>
<ol>
<li>你可以买⼊⼀次股票和卖出⼀次股票，并⾮每天都可以买⼊或卖出⼀次，总共只能买⼊和卖出⼀次，且买⼊必须在卖出的前⾯的某⼀天</li>
<li>如果不能获取到任何利润，请返回 0</li>
<li>假设买⼊卖出均⽆⼿续费</li>
</ol>
<p>示例1：<br>
输⼊：<br>
返回值: 5<br>
说明: 在第3天(股票价格 = 2)的时候买⼊，在第6天(股票价格 = 7)的时候卖出，最⼤利润 = 7-2 = 5，不能选择在第2天买⼊，第3天卖出，这样就亏损7了；同时，你也不能在买⼊前卖出股票。</p>
<p>示例2：<br>
输⼊：<br>
返回值: 2</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴穷举">暴⼒穷举</h3>
<p>这⾥涉及的节点⽆⾮是买⼊，卖出，那么我们遍历所有的数据，作为买⼊⽇期，同时将该⽇期后⾯每⼀个都作为卖出⽇期来计算，只要维护最⼤的利润即可。</p>
<pre><code class="language-java">public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int maxProfit = 0;
int n = prices.length;
// 外层循环：遍历所有可能的买入点
for (int i = 0; i < n - 1; i++) {
// 内层循环：遍历所有可能的卖出点（必须在买入点之后）
for (int j = i + 1; j < n; j++) {
int profit = prices - prices;
if (profit > maxProfit) {
maxProfit = profit;
}
}
}
return maxProfit;
}
}
</code></pre>
<ul>
<li>时间复杂度： O(n2)</li>
<li>空间复杂度：O(1)</li>
</ul>
<h3 id="贪法最优解">贪⼼法（最优解）</h3>
<p>我们要想得到⼀个最⼤的利润，其实就是要两者差值最⼤。如果让差值最⼤，假设在当天卖出，那么什么时候买⼊最好呢？</p>
<p>当然是在前⾯找到最⼩的买⼊点，⽐如：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505181425636.png" alt="" loading="lazy"></p>
<p>⽽前⾯的最⼩值，其实我们在遍历的时候是可以不断维护的，所以我们只要遍历⼀次数组即可。</p>
<p><strong>关键思想：</strong></p>
<ul>
<li>最大利润 = 某日价格 - 该日之前的最低价格</li>
<li>只需维护两个变量：
<ul>
<li><code>minPrice</code>：遍历过程中遇到的最低价格</li>
<li><code>maxProfit</code>：当前能获得的最大利润</li>
</ul>
</li>
</ul>
<pre><code class="language-java">public class Solution63 {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int result = 0;
for (int value: prices) {
// 维护最⼩值
min = Math.min(min, value);
// 当前值减去前⾯最⼩值，与利润最⼤值对⽐，维护好利润最⼤值
result = Math.max(result, value - min);
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需遍历一次数组</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数空间</li>
</ul>
<p>执行过程示例（prices = ）</p>
<pre><code class="language-text">i=0: price=8, minPrice=8, maxProfit=0
i=1: price=9, minPrice=8, maxProfit=1
i=2: price=2, minPrice=2, maxProfit=1
i=3: price=5, minPrice=2, maxProfit=3
i=4: price=4, minPrice=2, maxProfit=3
i=5: price=7, minPrice=2, maxProfit=5
i=6: price=1, minPrice=1, maxProfit=5
结果：5
</code></pre>
<h3 id="动态规划">动态规划</h3>
<p>dp表示前i天的最大利润，状态转移基于前i-1天的结果</p>
<p><strong>状态定义：</strong></p>
<ul>
<li><code>minPrice</code>：前i天的最低价格</li>
<li><code>maxProfit</code>：前i天能获得的最大利润</li>
</ul>
<pre><code class="language-java">public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int minPrice = prices;
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// 状态转移方程：
// 前i天的最大利润 = max(前i-1天的最大利润, 第i天价格-前i-1天的最低价格)
maxProfit = Math.max(maxProfit, prices - minPrice);
minPrice = Math.min(minPrice, prices);
}
return maxProfit;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，单次遍历</li>
<li><strong>空间复杂度</strong>：O(1)，优化后只需两个变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19588064
頁:
[1]