共计 1021 个字符,预计需要花费 3 分钟才能阅读完成。
1. 交易股票的最佳时机
(以下均疏忽暴力求解)
一次遍历
策略:
既然只有一次交易,那么能够通过遍从来寻找最大的差值
过程:
graph TD
应用数组一一存储元素 --> 寻找前面元素的最低值 --> 更新并存储其差值
工夫复杂度:O(n)
空间复杂度:O(1)
public class Solution {public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {if (prices[i] < minprice) {minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
2. 交易股票的最佳时机 II
贪婪算法
策略:
- 隔日上涨:明天买入,今天卖出
- 多日上涨:持有股票到最高点再卖出
- 隔日 / 多日上涨:不交易
graph TD
遍历数组 --> 若数值递增则直至上涨的前一天卖出 --> 若数值递加则不交易 --> 统计利润总值
工夫复杂度:O(n)
空间复杂度:O(1)
class Solution {public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {int tmp = prices[i] - prices[i - 1];
if (tmp > 0) profit += tmp;
}
return profit;
}
}
3. 交易股票的最佳时机 III
工夫复杂度:O(n)
空间复杂度:O(1)
var maxProfit = function(prices) {
const n = prices.length;
let buy1 = -prices[0], buy2 = -prices[0];
let sell1 = 0, sell2 = 0;
for (let i = 1; i < n; i++) {buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
};
4. 交易股票的最佳时机 IV
5. 最佳交易股票机会含冷冻期
6. 交易股票的最佳时机含手续费
正文完