前言

代码随想录算法训练营day31

一、Leetcode 455.分发饼干

1.题目

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

对每个孩子 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. 1 <= g.length <= 3 * 104
2. 0 <= s.length <= 3 * 104
3. 1 <= g[i], s[j] <= 231 - 1

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/assign-cookies

2.解题思路

方法一：排序 + 双指针 + 贪心

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。证明如下。

假设有 mm 个孩子，胃口值分别是 g1g1 到 gmgm，有 nn 块饼干，尺寸分别是 s1s1 到 snsn，满足 gi≤gi+1gi≤gi+1 和 sj≤sj+1sj≤sj+1，其中 1≤i

假设在对前 i−1i−1 个孩子分配饼干之后，可以满足第 ii 个孩子的胃口的最小的饼干是第 jj 块饼干，即 sjsj 是剩下的饼干中满足 gi≤sjgi≤sj 的最小值，最优解是将第 jj 块饼干分配给第 ii 个孩子。如果不这样分配，考虑如下两种情形：

1. 如果 i<mi<m 且 gi+1≤sjgi+1≤sj 也成立，则如果将第 jj 块饼干分配给第 i+1i+1 个孩子，且还有剩余的饼干，则可以将第 j+1j+1 块饼干分配给第 ii 个孩子，分配的结果不会让更多的孩子被满足；
2. 
3. 如果 j<nj<n，则如果将第 j+1j+1 块饼干分配给第 ii 个孩子，当 gi+1≤sjgi+1≤sj 时，可以将第 jj 块饼干分配给第 i+1i+1 个孩子，分配的结果不会让更多的孩子被满足；当 gi+1>sjgi+1>sj 时，第 jj 块饼干无法分配给任何孩子，因此剩下的可用的饼干少了一块，因此分配的结果不会让更多的孩子被满足，甚至可能因为少了一块可用的饼干而导致更少的孩子被满足。

基于上述分析，可以使用贪心的方法尽可能满足最多数量的孩子。

首先对数组 gg 和 ss 排序，然后从小到大遍历 gg 中的每个元素，对于每个元素找到能满足该元素的 ss 中的最小的元素。具体而言，令 ii 是 gg 的下标，jj 是 ss 的下标，初始时 ii 和 jj 都为 00，进行如下操作。

对于每个元素 g[i]g[i]，找到未被使用的最小的 jj 使得 g[i]≤s[j]g[i]≤s[j]，则 s[j]s[j] 可以满足 g[i]g[i]。由于 gg 和 ss 已经排好序，因此整个过程只需要对数组 gg 和 ss 各遍历一次。当两个数组之一遍历结束时，说明所有的孩子都被分配到了饼干，或者所有的饼干都已经被分配或被尝试分配(可能有些饼干无法分配给任何孩子)，此时被分配到饼干的孩子数量即为可以满足的最多数量。

3.代码实现

```java class Solution { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int m = g.length, n = s.length; int count = 0; for (int i = 0, j = 0; i < m && j < n; i++, j++) { while (j < n && g[i] > s[j]) { j++; } if (j < n) { count++; } } return count; } }
```

二、Leetcode 376. 摆动序列

1.题目

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

1. 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
2. 相反，[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. 1 <= nums.length <= 1000
2. 0 <= nums[i] <= 1000

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/wiggle-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

1. 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
2. 相反，[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. 1 <= nums.length <= 1000
2. 0 <= nums[i] <= 1000

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/wiggle-subsequence

2.解题思路

方法一：动态规划

思路及解法

每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。那么列出状态表达式为：

1. up[i]up[i] 表示以前 ii 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。
2. 
3. down[i]down[i] 表示以前 ii 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。

下面以 up[i]up[i] 为例，说明其状态转移规则：

1. 当 nums[i]≤nums[i−1]nums[i]≤nums[i−1] 时，我们无法选出更长的「上升摆动序列」的方案。因为对于任何以 nums[i]nums[i] 结尾的「上升摆动序列」，我们都可以将 nums[i]nums[i] 替换为 nums[i−1]nums[i−1]，使其成为以 nums[i−1]nums[i−1] 结尾的「上升摆动序列」。
2. 
3. 当 nums[i]>nums[i−1]nums[i]>nums[i−1] 时，我们既可以从 up[i−1]up[i−1] 进行转移，也可以从 down[i−1]down[i−1] 进行转移。下面我们证明从 down[i−1]down[i−1] 转移是必然合法的，即必然存在一个 down[i−1]down[i−1] 对应的最长的「下降摆动序列」的末尾元素小于 nums[i]nums[i]。
4. 
5.     我们记这个末尾元素在原序列中的下标为 jj，假设从 jj 往前的第一个「谷」为 nums[k]nums[k]，我们总可以让 jj 移动到 kk，使得这个最长的「下降摆动序列」的末尾元素为「谷」。
6. 
7.     然后我们可以证明在这个末尾元素为「谷」的情况下，这个末尾元素必然是从 nums[i]nums[i] 往前的第一个「谷」。证明非常简单，我们使用反证法，如果这个末尾元素不是从 nums[i]nums[i] 往前的第一个「谷」，那么我们总可以在末尾元素和 nums[i]nums[i] 之间取得一对「峰」与「谷」，接在这个「下降摆动序列」后，使其更长。
8. 
9.     这样我们知道必然存在一个 down[i−1]down[i−1] 对应的最长的「下降摆动序列」的末尾元素为 nums[i]nums[i] 往前的第一个「谷」。这个「谷」必然小于 nums[i]nums[i]。证毕。

这样我们可以用同样的方法说明 down[i]down[i] 的状态转移规则，最终的状态转移方程为：

up[i]={up[i−1],nums[i]≤nums[i−1]max⁡(up[i−1],down[i−1]+1),nums[i]>nums[i−1]down[i]={down[i−1],nums[i]≥nums[i−1]max⁡(up[i−1]+1,down[i−1]),nums[i]

最终的答案即为 up[n−1]up[n−1] 和 down[n−1]down[n−1] 中的较大值，其中 nn 是序列的长度。

3.代码实现

```java class Solution { public int wiggleMaxLength(int[] nums) { int n = nums.length; if (n < 2) { return n; } int[] up = new int[n]; int[] down = new int[n]; up[0] = down[0] = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { up[i] = Math.max(up[i - 1], down[i - 1] + 1); down[i] = down[i - 1]; } else if (nums[i] < nums[i - 1]) { up[i] = up[i - 1]; down[i] = Math.max(up[i - 1] + 1, down[i - 1]); } else { up[i] = up[i - 1]; down[i] = down[i - 1]; } } return Math.max(up[n - 1], down[n - 1]); } }

```

三、Leetcode 53. 最大子序和

1.题目

给你一个整数数组 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

提示：

1. 1 <= nums.length <= 105
2. -104 <= nums[i] <= 104

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/maximum-subarray

2.解题思路

方法一：动态规划

思路和算法

假设 numsnums 数组的长度是 nn，下标从 00 到 n−1n−1。

我们用 f(i)f(i) 代表以第 ii 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

max⁡0≤i≤n−1{f(i)}0≤i≤n−1max{f(i)}

因此我们只需要求出每个位置的 f(i)f(i)，然后返回 ff 数组中的最大值即可。那么我们如何求 f(i)f(i) 呢？我们可以考虑 nums[i]nums[i] 单独成为一段还是加入 f(i−1)f(i−1) 对应的那一段，这取决于 nums[i]nums[i] 和 f(i−1)+nums[i]f(i−1)+nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

f(i)=max⁡{f(i−1)+nums[i],nums[i]}f(i)=max{f(i−1)+nums[i],nums[i]}

不难给出一个时间复杂度 O(n)O(n)、空间复杂度 O(n)O(n) 的实现，即用一个 ff 数组来保存 f(i)f(i) 的值，用一个循环求出所有 f(i)f(i)。考虑到 f(i)f(i) 只和 f(i−1)f(i−1) 相关，于是我们可以只用一个变量 prepre 来维护对于当前 f(i)f(i) 的 f(i−1)f(i−1) 的值是多少，从而让空间复杂度降低到 O(1)O(1)，这有点类似「滚动数组」的思想。

3.代码实现

```java class Solution { public int maxSubArray(int[] nums) { int pre = 0, maxAns = nums[0]; for (int x : nums) { pre = Math.max(pre + x, x); maxAns = Math.max(maxAns, pre); } return maxAns; } }
```