面试经典 150 题 （七）

从右往左遍历

class Solution {
    public int maxProfit(int[] prices) {
        Map<Integer, Integer> priceMap = new HashMap<Integer, Integer>();
        Integer leftMaxNum = null;
        for (int i = prices.length - 1; i >= 0; i--){
            if (leftMaxNum == null || leftMaxNum < prices[i]){
                leftMaxNum = prices[i];
            }
            priceMap.put(prices[i], leftMaxNum);
        }
        int maxMom = 0;
        for (Map.Entry<Integer, Integer>price : priceMap.entrySet()){
            if ((price.getValue() - price.getKey()) > maxMom){
                maxMom = price.getValue() - price.getKey();
            }
        }
        return maxMom;
    }
}