貪心也是一個很有意思的專題，能遇到很多神奇的思路。

但這個專題，leetcode也沒放Hard，果然是怕這種玄學專題上點難度大家罩不住。那就很快了，直接過

763. Partition Labels[Medium]

思路：將字母串分組，相同字母必須放一組，求能分出的最多組及分組方案。這個直接預處理一下每個字母最后出現的位置，然后按位貪心，將結束為止延伸到每位的最遠位置，如果當前子串內所有最遠位置都被包進來了，就可以重新開一個新組了

五年前也做過這題，作為一個典型的預處理題型來做了

LeetCodeGOGOGO刷題記04——代碼優化（預處理）_leetcode 預處理-CSDN博客

/*
Author Owen_Q
*/
public class LabelsPatitioner {public static List<Integer> partitionLabels(String s) {List<Integer> result = new ArrayList<>();int[] lastPosition = new int[26];int len = s.length();for (int i = 0; i < len; i++) {lastPosition[s.charAt(i) - 'a'] = i;}int st = 0;int en = 0;for (int i = 0; i < len; i++) {en = Math.max(en, lastPosition[s.charAt(i) - 'a']);if (i == en) {result.add(en - st + 1);st = i + 1;}}return result;}
}

55. Jump Game[Medium]

思路：給定一個一位區域，從起點開始，每個位置有一個最遠到達距離，判斷能否到達終點。

這個沒什么說的，直接貪心最遠位置即可，如果到不了終點就停

/*
Author Owen_Q
*/
public class JumpGameReachable {public static boolean canJump(int[] nums) {int maxLen = 0;int len = nums.length;for (int i = 0; i < len; i++) {if (i > maxLen) {return false;}maxLen = Math.max(maxLen, i + nums[i]);}return true;}
}

45. Jump Game II[Medium]

思路：和上一題類似，不過這次保證能到終點，求最少要走的步數。

同樣是貪心，這次貪每步能走的最遠區域。每次貪心，從上次貪心所獲得的區域內能走到的最遠區域都可以成為本次貪心的結果。最后注意一下，由于題目保證一定能到達終點，且不會走出終點，則終點處一定只能走零步，因此終點不用計入貪心范圍，否則會多算一步。

/*
Author Owen_Q
*/
public class JumpGameFast {public static int jump(int[] nums) {int len = nums.length;int en = 0;int maxLen = 0;int step = 0;for (int i = 0; i < len - 1; i++) {maxLen = Math.max(maxLen, i + nums[i]);if (i == en) {step++;en = maxLen;}}return step;}
}

121. Best Time to Buy and Sell Stock[Easy]

思路：最后來看看這個Easy的貪心，也是很好奇，能怎么個Easy程度

股票題，低價買入，高價賣出，給定一段時間的股票價格，求最高收益。那這確實都不用動腦子，維護一下當前位置的最低價格和從最低價格開始買入當天賣出的最高收益即可

/*
Author Owen_Q
*/
public class StockTrader {public static int maxProfit(int[] prices) {int len = prices.length;int maxProfit = 0;int minPrice = prices[0];for (int i = 1; i < len; i++) {maxProfit = Math.max(maxProfit, prices[i] - minPrice);minPrice = Math.min(minPrice, prices[i]);}return maxProfit;}
}

完結撒花