[贪心_3] 摆动序列 | 最长递增子序列

目录

1.摆动序列

贪心

2.最长递增子序列

动态规划

贪心

---

找规律 优化dp

1.摆动序列

链接：376. 摆动序列

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

• 例如， [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) 。

---

之前我们用动态规划有写到过，现在我们来看一下 用贪心怎么写呢~

动态规划回顾

• for for 两层循环打表（由 j 到 i）
• 满足 if 写表

代码：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n=nums.size(),ret=1;vector<int> f(n,1);auto g=f;for(int i=0;i<n;i++){for(int j=0;j<=i-1;j++){if(nums[j]<nums[i])f[i]=max(f[i],g[j]+1);if(nums[j]>nums[i])g[i]=max(g[i],f[j]+1);ret=max(ret,max(f[i],g[i]));}}return ret;}
};

摆动序列就是一上一下。注意仅有一个元素或者含两个不等元素的序列也视作摆动序列，返回摆动序列 的 最长子序列的长度。

贪心

• 贪最值点+两端点

这里我们就不写具体的数了，而把数当成折线图的形式。目前先不考虑水平这样的形式，先考虑相邻两个元素不同的形式，最后在把水平的处理一下

如果图是这样的，如何找它的最长摆动序列呢？
我们肯定有这样的想法，把左边和右边的点挑出来，然后在把所有极大值点和极小值点也挑出来，所形成的序列就是一个最长摆动序列。

这个策略确实是可以的，我们的贪心策略最终也和这个策略长的一样。

• 接下来我们就来贪一下，我们要找到的是最长摆动序列，相当于就是在这个图中尽可能的挑一些点出来所形成的序列是摆动序列。
• 既然是尽可能挑多的点，那第一个点就给选上，接下来挑选第二个点的时候继续贪，当前右边这么多点我选择那个点看起来是最优的，此时就有分情况讨论的过程
• 第一种情况在上升的线上选一个点，但是在上升的这条线上选都没有第三种情况好，因为选了上升线上一个点接下来要去选下降的，如果挑选这些较小上升的点，那在挑选下降的点可供选择的空间就小了。比如画×的点就选不到了。
  第二种情况选择右边的某个点，如果选了这个点，那摆动系列绝对不可能是最长的，因为中间还有可以选择的一上一下的点。
• 同样选了这个点也会错失一个拐点，那摆动序列也不会是最长的。

可能还会选这条下降线的点，有可能是会最长的，但是并不保险，有可能这条线没有点，所以不如选第三种情况这个点。

• 固定两个点之后，考虑第三个点依旧和选择第二个点一样分情况讨论，如果是下降选择不能在下降的点，如果是上升选择不能在上升的点。直到所有点都选完，就是最长摆动子序列。
• 你会发现我们贪心挑选出来的点就是把极大值和极小值还有两个端点的值跳出来。

贪心：统计出所有的波峰以及波谷的个数
然后在把左右两个点加上就可以了。

那如何统计出最终的结果呢？

1. 首先如何确定一个点是波峰还是波谷，

• 波峰：当前这个点减左边的点如果是正，右边的点减去当前的点如果是负，就是波峰。
• 波谷：当前这个点减去左边的点如果是负，右边的点减去当前的点如果是正，就是波谷。
• 也就是说当前这个点左右是相反的就可以确定要么是波峰要么是波谷。

• 2. 还有一个问题，如果相邻两个元素是相同的就麻烦了，它会分成两大类，
  第一类：相同的时候左右增减趋势是相同的
  第二类：相同的时候左右增减趋势是相反的

第一类是没有波峰波谷的，第二类是有的。

虽然是有相同的元素，但是

• 第一类总体要么上升、要么下降，不需要统计波峰波谷。
• 第二类要么下降后上升、要么上升后下降，是需要统计波峰波谷的。

但是相同元素该统计那一个呢？

• 并且虽然属于不同类
• 但是都是左边是是负数右边是0一个不需要统计一个需要统计，还是很恶心的。

可以用一个变量left记录当前某个点左边的增减趋势，然后上述情况的时候，把这些相同的情况都可以忽略掉~仅需考虑最左边点的增减趋势和最右边点的增减趋势。

接下来模拟一下，

left就是标记某个点左边的正负，它有三种情况

• left = 0（表示第一个点左边既可以上升也可以是下降的）
  left > 0（上升）
  left < 0（下降）

然后确定某个点的时候仅需算一个它的右边right就行了，right = nums[i+1] - nums[i]
，当left*right <= 0 就是波峰或者波谷，当right = 0 说明遇到相同的元素然后是可以抛弃的，

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int left=0,ret=0,n=nums.size();for(int i=0;i<n-1;i++){int right=nums[i+1]-nums[i];if(right==0) continue;if(right*left<=0)ret++;left=right;}return ret+1;//+最后位置}
};

证明：

这道题证明有三种方法：

1. 反证法
2. 分类讨论
3. 交换论证法

这里我们证明方法是反证法：

• 假设我们的操作是错的，此时它的反命题就是一个正确的，只要我们证明正确的命题是有矛盾的或者有错误的，那原来的命题就是正确的。
• 我们的贪心解是选择左右端点和极值，假设最后选择的点为n，这里 n = 6
• 假设贪心解是错的，那必须会存在一个最优解，在相同的情况下可以选择更多的点，N > 6。
• 我们只要推出最优解是矛盾的或者错误的，那我们贪心解就对了。

盯着每一个拐点，先看最左边的拐点，我们这是一个连续的区间，左边元素比它小，右边元素也比它小，在它这个左右区间里一定会出现一个极大值，要么该点是极大值点要么就是区间内的其他点。

• 在看下一个拐点，左右两侧都是比它大的，又因为是连续的，所以在这个区间里面必定会存在一个极小值。

同理后面也可以得到极大值，极小值。

• 因此可以推出在最优解里，极值点个数是N-2（舍去左右两端点），但是这个N-2是不存在的。
• 因为在贪心解里面我们是可以推出来极值点个数是n-2=4，因为最优解N>6，所以它的极值点个数是N-2 > 4的，但是极值点个数是不可能大于4的，所以最优解压根就是不存在的
• 因为贪心解得到极值点个数是4，你这个最优解算出考虑极值点个数大于4，这是不符合实际情况的。

所以这个最优解是不存在的，因此贪心解是正确的。

---

2.最长递增子序列

链接： 300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

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

---

动态规划

• 变化的状态机

class Solution {
public:int lengthOfLIS(vector<int>& nums) {//每一步 最长int n=nums.size();vector<int> dp(n,1);for(int i=1;i<n;i++){int tmp=1;for(int j=0;j<=i-1;j++){if(nums[j]<nums[i]){tmp=max(tmp,dp[j]);dp[i]=tmp+1;}}}int ret=0;for(int i=0;i<n;i++){ret=max(ret,dp[i]);}return ret;  }
};

贪心

听懂这道题一定要把动态规划里面这道题解法搞清楚，我们的贪心策略其实是基于动态规划的解法

• 就是动态规划的解法的过程中发现可以用贪心优化的地方。
• 还有优选算法那里的二分查找搞清楚。

我们这里的贪心策略是要用这两个东西。

1. 回顾 dp 的解法

• 状态表示：dp[i] 表示：以 i 位置的元素为结尾的所有子序列中， 最长递增子序列的长度
• 状态转移方程：dp[i] = max(dp[j] + 1) (j < i && nums[j] < nums[i])

更新dp[i] 的值，就是拿着nums[i] 去前面找，当找到一个位置发现这个位置的值，nums[j] < nums[i] 说明 i 可以拼在 j 的后面，此时就用这个dp[j]也就是以 j 位置为结尾的最长递增子序列的长度 然后 + 1 更新 dp[i] 的值。当把前面都找完此时dp[i]的值就是以 i 位置的元素为结尾的所有子序列中， 最长递增子序列的长度。

• 最核心的操作中，我们会发现一个性质：我们在考虑最长递增子序列的 “长度” 的时候，并不关心你这个序列长什么样子，我们仅关心你的 “最后一个元素” 是谁。

2. 贪心优化

接下来我们用一个例子模拟一下贪心过程

• 从前到后扫描每一个元素，当扫描第一个位置的元素时候其实我们得到一个长度为1 的序列长什么样子。
• (但是我们只关心递增子序列长度为x中最后一个元素，并不关心序列长什么样子)，这一点在上面已经说过了。

我们来贪心的模拟 一下 这个扫描过程：

扫描到3的时候发现，3是接不到7后面，所以3这个元素单独形成一个长度为1的序列，现在又找到一个长度为1的序列最后一个元素是3。此时贪心策略就来了，当我发现长度为1递增子序列有两个的时候，较大的就没有必要存了。

• 原因就是，所有能接到7后面的数，铁定能接到3这个数的后面，所以我们不需要存较大的7，仅需存较小的3就可以判断后面的数是否能拼到长度为1的序列后面。
• 这里就是我们的第一个贪心策略，存最后一个元素的时候，仅需存储最小值。

扫描8的时候，此时第二个贪心策略来了。我们其实有两种策略，第一种让8单独形成一个长度为1的序列，第二种要么让8拼到3的后面形成一个长度为2的序列。此时我们贪心选择第二种策略。因为要找最长递增子序列。

• 扫描到4，发现4能放到长度为1的3后面，但是不放，太浪费了，所以往下放，发现4可以自己形成一个长度为2，但是发现4小于8，所以贪心把8干掉，把4放好。
• 上面的过程就是，发现4能放到长度为1的3后面，但是不放。往下放，发现4能不能放到8后面，就把4放到这里，同时利用第二个贪心策略只存最小值的时候，把8干掉，4留下。

扫描到7，也是一样，7能拼到3后面就不放，7能拼到4后面也不放，所以7形成一个长度为3的序列
扫描到2，发现2拼不到3后面，只能把2放到长度为1，但是2比3小，能拼接到3后面一定能拼接到2后面，所以3干掉，保留2

• 扫描到14，发现能拼接到2，4，7后面但是都不放，所以14单独形成一个长度为4的序列
• 扫描到13，发现能拼接到2，4，7后面但是不放，不能放14后面，就放14后面，同时13比14小，14干掉，13保留

---

当整个数组扫描完，我们发现长度仅从1更新到4，所以最长递增子序列的长度就是4。

• 虽然这里拼接的序列并不是最终的序列，但是能统计到4，就是我们的最长递增子序列的长度。
• 这里我们总结一下贪心策略：
• 我们的贪心策略就体现在两个地方：存什么，存哪里

这里的贪心策略的提出就是交换论证法的思想，比如能拼接7的后面的数，铁定能拼接到3的后面，这不就是交换论证吗。

• 这里已经说明为什么贪心策略是对的，但是我们分析一下贪心的时间复杂度，存什么肯定是拿一个数组去存，下标为0存长度为1的最小值、下标为1存长度为2的最小值…
• 最耗时的就是存哪里，如果是来了一个数从前往后扫描比较时间复杂度是O(n)，那整体时间复杂度还是O(N^2)，这个好像和动规是一样的。那还贪心什么呢？比动规还难理解。

我们还可以发现，我们贪心得到的数组，其实还有优化的地方

利用二分优化

我们发现存长度为x的最小值数组里面的值是递增有序的。

此时我们在找存哪里插入位置的时候，可以用二分快速找到插入位置。

• 假设来一个x，我们要找的是所有大于等于x的最小值，右边都是大于等于x，左边是小于x，这就有了二段性。就可以用二分查找了。
• 证明数组是递增的。

直接证明：

第一个元素来了直接就是一个点，第二个元素来发现

• 能拼在第一个元素后面所以重新开一个点
• 如果不能放就把这个元素覆盖到原始元素

这里有个不等关系，这个元素大于前一个元素，小于后一个元素。递增是不会改变的。

回归一下二分，定义一个left，right，mid，如果mid落在左边 left = mid + 1，如果mid落在右边有可能是结果 right = mid，等到循环解决，left或者right就是要插入的位置。

二分代码示例：

class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right)//单调无重复{int mid=left+(right-left)/2;//防溢出if(nums[mid]>target)right=mid-1;else if(nums[mid]<target)left=mid+1;elsereturn mid;}return -1;}
};

• 这里有个细节问题，再用二分的时候要考虑边界情况，因为我们要找的是大于等于nums[i]的最小值的位置，left和right其实是在这个数组中找，有没有这个数比这个数组中所有数都大，那此时应该是数组重新开一个空间，放在这个新开位置里
• 所以二分之前先判断 nums[i] > ret.back()，此时不用二分，直接放在数组后一个位置。
• 否则在二分寻找插入位置，覆盖前一个元素

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> ret;for(int i=0;i<nums.size();i++){if (ret.empty() || nums[i] > ret.back()) ret.push_back(nums[i]);else{//二分插入位置  n-->logNint left=0,right=ret.size()-1;while(left<=right){int mid=left+(right-left)/2;if(ret[mid]>=nums[i])right=mid;elseleft=mid+1;}ret[left]=nums[i]; //更新为 偏左的位置}}return ret.size();}
};