2020/3/15

題目描述

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

如果你最多只允許完成一筆交易（即買(mǎi)入和賣(mài)出一支股票），設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。

注意你不能在買(mǎi)入股票前賣(mài)出股票。

示例

示例：
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出，最大利潤(rùn) = 6-1 = 5 。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格。

示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。

相關(guān)標(biāo)簽

數(shù)組
動(dòng)態(tài)規(guī)劃

解題思路

• 算法：
  利用一個(gè) HashMap 來(lái)存儲(chǔ)第 i 天到最后一天之間的最高價(jià)格 max_price 和最大利潤(rùn) max_profit，第 i -1 天的最大利潤(rùn)便是 max(max_price - price[i-1], max_profit)。

• 復(fù)雜度分析：
  時(shí)間復(fù)雜度：O(N)
  空間復(fù)雜度：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
    }
}

執(zhí)行用時(shí) : 0 ms, 在所有 Rust 提交中擊敗了100.00%的用戶
內(nèi)存消耗 : 2.2MB, 在所有 Rust 提交中擊敗了33.33.00%的用戶

總結(jié)

本題為一系列動(dòng)態(tài)規(guī)劃的最簡(jiǎn)單形態(tài)，面試?？?。