day27：貪心part1，基礎篇

455.分發餅干

循環結束條件注意餅干比孩子多的情況

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int ans = 0;// idx控制胃口，i控制餅干int idx = 0;for (int i = 0; i < s.length && idx < g.length; i++) {if (s[i] >= g[idx]) {idx++;ans++;}}return ans;}
}

376.擺動序列

關鍵在于如何區分上下坡平坡和同方向平坡的情況

class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length == 1) return 1;// 理解為開始點左邊有一個平坡，使得可以從第一個節點開始遍歷邏輯int prediff = 0;int nextdiff = 0;// 默認最右邊是峰值點int ans = 1;for (int i = 0; i < nums.length - 1; i++) {nextdiff = nums[i + 1] - nums[i];if ((prediff >= 0 && nextdiff < 0) || (prediff <= 0 && nextdiff > 0)) {ans++;prediff = nextdiff;}}return ans;}
}

53.最大子數組和

class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];if (sum > ans) ans = sum;if (sum < 0) sum = 0;}return ans;}
}