算法日记day 28（贪心之分发饼干|摆动序列|最大子数组和|买卖股票最佳时机）

一、分发饼干

题目：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

 示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

思路：

可以采用双指针的方法，先将两数组从小到大排序，判断饼干数组中的值是否大于等于胃口数组的值，如果是结果加1，然后饼干数组向前遍历，继续判断，直到饼干数组全部遍历完毕，输出结果数组

代码：

public int findContentChildren(int[] g, int[] s) {
    // 首先对孩子的胃口数组 g 和饼干的数组 s 进行排序
    Arrays.sort(g); // 排序孩子的胃口数组
    Arrays.sort(s); // 排序饼干数组
 
    int index = s.length - 1; // 初始化饼干数组的指针，指向最大的饼干
    int result = 0; // 初始化结果，记录满足条件的孩子数量
 
    // 从胃口最大的孩子开始向前遍历
    for (int i = g.length - 1; i >= 0; i--) {
        // 如果饼干指针有效且当前饼干能够满足当前孩子的胃口
        if (index >= 0 && s[index] >= g[i]) {
            result++; // 记录当前孩子可以被满足
            index--; // 饼干指针向前移动，指向下一个更小的饼干
        }
    }
    return result; // 返回满足条件的孩子数量
}

1. 排序数组：首先通过 Arrays.sort() 方法对孩子的胃口数组 g 和饼干数组 s 进行排序。排序的目的是为了优化后续的分配过程，使得从胃口最大的孩子开始分配饼干。

2. 初始化指针和结果：

   • index 初始化为 s.length - 1，即指向饼干数组中最大的饼干。这样可以从大到小依次分配饼干。
   • result 初始化为 0，用于记录能够被满足的孩子数量。

3. 遍历分配饼干：

   • 使用 for 循环从胃口最大的孩子开始向前遍历 g 数组。
   • 在每次迭代中，检查当前的饼干指针 index 是否有效（大于等于 0），并且当前指向的饼干 s[index] 是否能够满足当前孩子的胃口 g[i]。
   • 如果满足条件，即 s[index] >= g[i]，则将 result 自增 1，表示当前孩子可以被满足。
   • 然后将 index 向前移动一位，指向下一个更小的饼干，继续寻找下一个可以满足的孩子。

二、摆动序列

题目：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

思路：

在判断是否摆动时，需要判断当前节点与左右邻节点的差值是否为一正一负，满足条件才是属于摆动，其中存在一种特殊情况，如：（1,2,2,4,5）属于单调摆动，这种情况总共只有2个摆动，即为边界的两次摆动，因此采用双指针摆动时不能实时更新两个指针的位置，应为一个指针负责判断差值，当差值存在时才能更新另一个指针的位置

代码：

public int wiggleMaxLength(int[] nums) {
    int prediff = 0; // 上一个数字之间的差值
    int curdiff = 0; // 当前数字之间的差值
    int result = 1; // 初始长度至少为1，因为数组至少有一个元素
 
    if (nums.length == 1)
        return 1; // 如果数组长度为1，直接返回1作为最大长度
 
    for (int i = 1; i < nums.length; i++) {
        curdiff = nums[i] - nums[i - 1]; // 计算当前数字与前一个数字的差值
 
        // 判断是否构成摆动
        if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)) {
            result++; // 如果当前差值和上一个差值方向相反，则增加摆动序列的长度
            prediff = curdiff; // 更新上一个差值为当前差值，用于下一次比较
        }
    }
 
    return result; // 返回最长摆动子序列的长度
}

1. 变量说明：

   • prediff：存储上一对相邻数字之间的差值。
   • curdiff：存储当前对相邻数字之间的差值。
   • result：记录最长摆动子序列的长度，初始化为1，因为至少可以包含数组中的第一个元素。

2. 特殊情况处理：

   • 如果数组长度为1，直接返回1，因为单个元素本身就构成一个摆动序列。

3. 遍历数组：

   • 从数组的第二个元素开始遍历到最后一个元素。
   • 计算当前相邻元素的差值 curdiff = nums[i] - nums[i - 1]。

4. 判断摆动条件：

   • 如果当前差值 curdiff 和上一个差值 prediff 的方向相反（值的正负），则说明这两个数字构成了一个摆动。摆动的条件是：当 prediff >= 0 且 curdiff < 0 或者 prediff <= 0 且 curdiff > 0。
   • 如果满足摆动条件，则增加 result 的值，并更新 prediff 为 curdiff，若不满足摆动（即为平坡时），继续移动curdiff，不更新prediff的位置，以便下一轮比较。

三、最大子数组和 

题目：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

思路：

判断最大子数组和时，如果子数组总和已经小于0，这时继续相加只会让后面的总值变小，因此当总和小于0时，就不需要继续往下相加，而是以下一个值为起始位置重新统计子数组和，同时记录当前遍历的情况中出现的最大子数组和，最后返回结果

代码：

public int maxSubArray(int[] nums) {
    int result = Integer.MIN_VALUE; // 初始化结果为整型最小值，用于记录最大子数组和
    int count = 0; // 记录当前子数组的和
 
    for (int i = 0; i < nums.length; i++) {
        count += nums[i]; // 将当前元素加入到当前子数组和中
 
        if (count > result)
            result = count; // 更新最大子数组和的结果
 
        if (count < 0)
            count = 0; // 如果当前子数组和为负数，说明当前子数组不可能为最大子数组的前缀，重置为0
    }
 
    return result; // 返回最大子数组和
}

1. 变量说明：

   • result：用来存储当前找到的最大子数组和，初始值设为整型最小值，确保可以正确比较后续的和。
   • count：记录当前子数组的累积和。

2. 循环遍历数组：

   • 使用 for 循环遍历数组 nums。
   • 在每次循环中，将当前元素 nums[i] 加入到 count 中，表示扩展当前子数组。

3. 更新最大子数组和：

   • 每次更新 count 后，通过 if (count > result) 判断当前 count 是否大于 result，如果是，则更新 result。

4. 处理负数子数组：

   • 如果 count 小于0，意味着当前累积的子数组和已经为负数，不可能对后续的子数组和有正的贡献，因此将 count 重置为0，表示舍弃当前子数组，重新开始计算新的子数组。

5. 返回结果：

   • 最后返回 result，即为数组中最大的子数组和。

四、买卖股票最佳时机

题目：

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

思路：

关键在于如何寻找这个最小最大值，利用贪心的思维，当局部变量为最优解时，全局变量便等于所有最优的局部变量解之和，因此，我们只需要判断相邻两个数之间的差值，如果为正数，则加入局部的利润中，为负数，则舍去，这样所有的局部正数相加得到的全局总利润即为最优解

代码：

public int maxProfit(int[] prices) {
    int result = 0; // 初始化最大利润为0
 
    // 遍历股票价格数组
    for (int i = 1; i < prices.length; i++) {
        // 计算相邻两天的价格差
        int profit = prices[i] - prices[i - 1];
 
        // 如果价格差大于0，表示可以有利润，累加到result中
        if (profit > 0) {
            result += profit;
        }
        // 如果价格差小于等于0，则说明当天卖出的话无法获得利润，跳过此次交易
    }
 
    return result; // 返回最大利润
}

1. 变量说明：

   • result：用来存储最终的最大利润，初始值为0，因为开始时没有进行任何交易，利润自然为0。

2. 循环遍历价格数组：

   • 使用 for 循环遍历数组 prices，从第二天开始（即 i = 1）到最后一天。
   • 在每次循环中，计算相邻两天的价格差 profit，即 prices[i] - prices[i - 1]。

3. 判断利润是否为正：

   • 如果 profit > 0，表示当天卖出股票可以获得利润，将这个利润累加到 result 中。
   • 如果 profit <= 0，表示当天卖出股票无法获得利润（或者可能损失），则跳过此次交易，不对 result 进行累加操作。

4. 返回结果：

   • 最后返回累积的 result，即为股票买卖能够获得的最大利润。

今天的学习就到这里