2020/3/15
题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例
示例：
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
相关标签
数组
动态规划
解题思路
-
算法：
利用一个 HashMap 来存储第 i 天到最后一天之间的最高价格 max_price 和最大利润 max_profit，第 i -1 天的最大利润便是 max(max_price - price[i-1], max_profit)。
-
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N)
源代码
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let (mut res, len) = (0, prices.len());
if len == 0 {
return 0;
}
// vec[(max_price, max_profit)]
let mut max_profit_store: Vec<(i32, i32)> = vec![(prices[len-1], 0);len];
for i in (0..len-1).rev() {
let (max_price, max_profit, cur_price) =
(max_profit_store[i+1].0, max_profit_store[i+1].1, prices[i]);
max_profit_store[i] = if cur_price < max_price {
(max_price, std::cmp::max(max_profit, max_price-cur_price))
}
else {
(cur_price, max_profit_store[i+1].1)
};
res = std::cmp::max(res, max_profit_store[i].1);
}
res
}
}
执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.2MB, 在所有 Rust 提交中击败了33.33.00%的用户
总结
本题为一系列动态规划的最简单形态，面试常客。
