理论基础
题目链接/文章讲解：代码随想录
视频讲解：贪心算法理论基础！_哔哩哔哩_bilibili
455.分发饼干
题目链接/文章讲解：代码随想录
视频讲解：贪心算法，你想先喂哪个小孩？| LeetCode：455.分发饼干_哔哩哔哩_bilibili
一开始使用了双重循环，时间复杂度为
(
O
(
n
×
m
)
)
(O(n \times m))
(O(n×m))，其中
(
n
)
(n)
(n) 是 g 的长度，
(
m
)
(m)
(m) 是 s 的长度，会超出时间限制。我们可以通过使用双指针的方法将时间复杂度优化到
(
O
(
n
+
m
)
)
(O(n + m))
(O(n+m))。
class Solution {
public int findContentChildren(int[] g, int[] s) {
// 首先对两个数组进行排序
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int i = 0; // 指向孩子的指针
int j = 0; // 指向饼干的指针
// 使用双指针遍历两个数组
while (i < g.length && j < s.length) {
if (s[j] >= g[i]) {
// 如果当前饼干可以满足当前孩子，则计数加一，并且两个指针都向前移动
count++;
i++;
j++;
} else {
// 如果当前饼干不能满足当前孩子，则只移动饼干的指针
j++;
}
}
return count;
}
}
376. 摆动序列
题目链接/文章讲解：代码随想录
视频讲解：贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列_哔哩哔哩_bilibili
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int prevDiff = nums[1] - nums[0];
int count = prevDiff != 0 ? 2 : 1; // 如果前两个数相同，则摆动序列长度为1，否则为2
for (int i = 2; i < nums.length; i++) {
int currDiff = nums[i] - nums[i - 1];
if ((currDiff > 0 && prevDiff <= 0) || (currDiff < 0 && prevDiff >= 0)) {
count++;
prevDiff = currDiff;
}
}
return count;
}
}
53. 最大子序和
题目链接/文章讲解：代码随想录
视频讲解：贪心算法的巧妙需要慢慢体会！LeetCode：53. 最大子序和_哔哩哔哩_bilibili
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE; // 初始化最大和为最小整数值
int sum = 0; // 初始化当前子数组的和为0
for (int i = 0; i < nums.length; i++) {
sum += nums[i]; // 累加当前元素到当前子数组的和
// 更新最大和
if (sum > maxSum) {
maxSum = sum;
}
// 如果当前子数组的和为负数，重置为0
if (sum < 0) {
sum = 0;
}
}
return maxSum;
}
}