貪心算法理論基礎：
貪心算法沒有類似遞歸、回溯的套路。主要的思想可以理解為：用局部最優找全局最優。
#LeetCode 455. Assign Cookies
#LeetCode 455. 視頻講解：貪心算法，你想先喂哪個小孩？| LeetCode：455.分發餅干_嗶哩嗶哩_bilibili
題目需要考慮局部最優，在這個題目中是大餅干盡可能分給胃口大的，充分利用餅干尺寸，全局最優是分給盡可能多的小孩。
注意用if 來表示某個條件，如果用while 會出現重復計數的問題。
代碼：
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int result = 0;int index = s.length - 1;for (int i = g.length - 1; i >= 0; i--) {if (index >= 0 && g[i] <= s[index]) {result ++;index --;}}return result;}
}#LeetCode 376. Wiggle Subsequence
#LeetCode 376. 視頻講解：貪心算法，尋找擺動有細節！| LeetCode：376.擺動序列_嗶哩嗶哩_bilibili
如果使用prediff 表示第二個數字與第一個數字的差值，curdiff 表示第三個數字與第二個數字的差值，那么存在，
滿足條件的情況1 ：prediff(nums[i] - nums[i - 1]) >= 0 同時?curdiff(nums[i + 1] - nums[i]) < 0
滿足條件的情況2 ：prediff(nums[i] - nums[i - 1] <= 0 同時?curdiff(nums[i + 1] - nums[i]) > 0。
如果curdiff 等于0，那么代表后兩個元素相同，是不滿足擺動條件的，所以只有prediff 可以等于0。那么會存在：[1, 2, 2, 1] 這樣的情況擺動是3，還有情況是[1, 2] 這樣的擺動是2，還有一種是[1, 2, 2, 2, 3, 4]?這樣的情況擺動是2。針對最后一個情況，采取的方式是：prediff = curdiff; 這行代碼的執行是在滿足擺動條件時。
代碼：
class Solution {public int wiggleMaxLength(int[] nums) {int prediff = 0, curdiff = 0;int result = 1;for (int i = 0; i < nums.length - 1; i++) {curdiff = nums[i+1] - nums[i];if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)) {result ++;prediff = curdiff;}}return result;}
}#LeetCode 53. Maximum Subarray
#LeetCode 53. 視頻講解：貪心算法的巧妙需要慢慢體會！LeetCode：53. 最大子序和_嗶哩嗶哩_bilibili
如果是[-2,-1]，添加這一行代碼：result = Math.max(sum, result);?這一行代碼的意義是在每一次循環迭代中更新并維護最大子數組和的當前最優值。遇到連續和負數，才重新計算，而不是遇到負數就重新計算。如果遇到連續和負數，代表會造成最終的值變小。
代碼：
class Solution {public int maxSubArray(int[] nums) {int result = Integer.MIN_VALUE;int sum = 0;if (nums.length == 1) {return nums[0];}for (int i = 0; i < nums.length; i++) {sum += nums[i];result = Math.max(sum, result);if (sum > 0) {if (result < sum) {result = sum;}}else {sum = 0;}}return result;}
}
)
