貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)意乓，總是做出在當(dāng)前看來是最好的選擇烫罩。也就是說惜傲，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解贝攒。
貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解盗誊，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性隘弊，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)哈踱，只與當(dāng)前狀態(tài)有關(guān)。
貪心算法基本思路
- 建立數(shù)學(xué)模型來描述問題
- 把求解的問題分成若干個(gè)子問題
- 對(duì)每個(gè)子問題求解梨熙，得到子問題的局部最優(yōu)解
- 把子問題的解局部最優(yōu)解合成原來問題的一個(gè)解
各題題解：
// ###### [買賣股票的最佳時(shí)機(jī)](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
public int maxProfit(int[] prices) {
//思路：遍歷一遍嚣鄙，記錄一個(gè)最小值，如果當(dāng)前不是最小值串结，那么與最小值做差哑子，假定在這天賣舅列，記錄一個(gè)最大利潤
int minPrice = prices[0];
int maxProfit = 0;
for (int i=1;i<prices.length;i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
//那么假如在這天賣，記錄當(dāng)前的差價(jià)
maxProfit = Math.max(prices[i]-minPrice, maxProfit);
}
}
return maxProfit;
}
// ###### [買賣股票的最佳時(shí)機(jī) II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)
/**
* 只要有漲幅區(qū)間卧蜓，都要吃掉股價(jià)漲幅
*/
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) {
//只要后一天股價(jià)比前一天高帐要，都要累計(jì)收益
profit += dif;
}
}
return profit;
}
// ###### [跳躍游戲](https://leetcode.cn/problems/jump-game/)
/**
* 思路：貪心算法
* 只要存在一個(gè)位置x，它本身可以到達(dá)弥奸，并且它跳躍的最大長度為 x+nums[x]榨惠，這個(gè)值大于等于y，即 x+nums[x]≥y盛霎，那么位置 y 也可以到達(dá)赠橙。
* 這樣以來，我們依次遍歷數(shù)組中的每一個(gè)位置愤炸，并實(shí)時(shí)維護(hù) 最遠(yuǎn)可以到達(dá)的位置期揪，如果 最遠(yuǎn)可以到達(dá)的位置 大于等于數(shù)組中的最后一個(gè)位置，就return true
*/
public boolean canJump(int[] nums) {
int n= nums.length;
int rightmost = 0; //定義當(dāng)次跳躍范圍能走的最遠(yuǎn)位置
for (int i=0;i<n;i++) {
if (i<=rightmost) {
//在當(dāng)次遍歷的最遠(yuǎn)范圍內(nèi)查找规个，看i位置能走的最遠(yuǎn)位置i+nums[i]能否刷新rightmost
rightmost = Math.max(rightmost, i+nums[i]);
if (rightmost >= n-1) {
return true;
}
}
}
return false;
}
