貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。

貪心算法不是對所有問題都能得到整體最優(yōu)解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關。

貪心算法基本思路

• 建立數(shù)學模型來描述問題
• 把求解的問題分成若干個子問題
• 對每個子問題求解，得到子問題的局部最優(yōu)解
• 把子問題的解局部最優(yōu)解合成原來問題的一個解

各題題解：

//            ###### [買賣股票的最佳時機](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
    public int maxProfit(int[] prices) {
        //思路：遍歷一遍，記錄一個最小值，如果當前不是最小值，那么與最小值做差，假定在這天賣，記錄一個最大利潤
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i=1;i<prices.length;i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                //那么假如在這天賣，記錄當前的差價
                maxProfit = Math.max(prices[i]-minPrice, maxProfit);
            }
        }
        return maxProfit;
    }

//            ###### [買賣股票的最佳時機 II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)
    /**
     * 只要有漲幅區(qū)間，都要吃掉股價漲幅
     */
    public int maxProfit2(int[] prices) {
        int profit = 0;
        for(int i=prices.length-1;i>0;i--) {
            int dif = prices[i] - prices[i-1];
            if(dif > 0) {
                //只要后一天股價比前一天高，都要累計收益
                profit += dif;
            }
        }
        return profit;
    }

    //            ###### [跳躍游戲](https://leetcode.cn/problems/jump-game/)

    /**
     * 思路：貪心算法
     * 只要存在一個位置x，它本身可以到達，并且它跳躍的最大長度為 x+nums[x]，這個值大于等于y，即 x+nums[x]≥y，那么位置 y 也可以到達。
     * 這樣以來，我們依次遍歷數(shù)組中的每一個位置，并實時維護 最遠可以到達的位置，如果 最遠可以到達的位置 大于等于數(shù)組中的最后一個位置，就return true
     */
    public boolean canJump(int[] nums) {
        int n= nums.length;
        int rightmost = 0; //定義當次跳躍范圍能走的最遠位置
        for (int i=0;i<n;i++) {
            if (i<=rightmost) {
                //在當次遍歷的最遠范圍內(nèi)查找，看i位置能走的最遠位置i+nums[i]能否刷新rightmost
                rightmost = Math.max(rightmost, i+nums[i]);
                if (rightmost >= n-1) {
                    return true;
                }
            }
        }
        return false;
    }