【贪心算法】（第三篇）
目录
最⻓递增⼦序列（medium）
题目解析
讲解算法原理
编写代码
递增的三元⼦序列（medium）
题目解析
讲解算法原理
编写代码
最⻓递增⼦序列（medium）
题目解析
1.题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
2.题目描述
给你⼀个整数数组 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
提⽰：
◦ 1 <= nums.length <= 2500
◦ -10(4) <= nums[i] <= 10(4)
讲解算法原理
解法（贪⼼）：
贪⼼策略：
我们在考虑最⻓递增⼦序列的⻓度的时候，其实并不关⼼这个序列⻓什么样⼦，我们只是关⼼最后⼀个元素是谁。这样新来⼀个元素之后，我们就可以判断是否可以拼接到它的后⾯。
因此，我们可以创建⼀个数组，统计⻓度为 x 的递增⼦序列中，最后⼀个元素是谁。为了尽可能的让这个序列更⻓，我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
统计的过程中发现，数组中的数呈现「递增」趋势，因此可以使⽤「⼆分」来查找插⼊位置。
编写代码
cc++算法代码：
class Solution
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i = 1; i < n; i++){if(nums[i] > ret.back()) // 如果能接在最后⼀个元素后⾯，直接放 {ret.push_back(nums[i]);}else{// ⼆分插⼊位置int left = 0, right = ret.size() - 1;while(left < right){int mid = (left + right) >> 1;if(ret[mid] < nums[i]) left = mid + 1;else right = mid;}ret[left] = nums[i]; // 放在 left 位置上 }}return ret.size();}
};java算法代码：
class Solution
{public int lengthOfLIS(int[] nums) {ArrayList<Integer> ret = new ArrayList<>();int n = nums.length;ret.add(nums[0]);for(int i = 1; i < n; i++){if(nums[i] > ret.get(ret.size() - 1)) // 如果能接在最后⼀个元素后⾯，直接放{ret.add(nums[i]);}else{// ⼆分插⼊位置int left = 0, right = ret.size() - 1;while(left < right){int mid = (left + right) / 2;if(ret.get(mid) < nums[i]) left = mid + 1;else right = mid;}ret.set(left, nums[i]); // 放在 left 位置上}}return ret.size();}
}递增的三元⼦序列（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组 nums ，判断这个数组中是否存在⻓度为 3 的递增⼦序列。
如果存在这样的三元组下标 (i, j, k) 且满⾜ i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
⽰例1：
输⼊：nums=[1,2,3,4,5]
输出：true
解释：任何i<j<k的三元组都满⾜题意
⽰例2：
输⼊：nums=[5,4,3,2,1]
输出：false
解释：不存在满⾜题意的三元组
⽰例3：
输⼊：nums=[2,1,5,0,4,6]
输出：true
解释：三元组(3,4,5)满⾜题意，因为nums[3]==0<nums[4]==4<nums[5]==6
提⽰：
◦ 1 <= nums.length <= 5 * 10(5)
◦ -2(31) <= nums[i] <= 2(31) - 1
讲解算法原理
解法（贪⼼）：
贪⼼策略：
最⻓递增⼦序列的简化版。
不⽤⼀个数组存数据，仅需两个变量即可。也不⽤⼆分插⼊位置，仅需两次⽐较就可以找到插⼊位置。
编写代码
c++算法代码：
class Solution
{
public:bool increasingTriplet(vector<int>& nums) {int a = nums[0], b = INT_MAX;for(int i = 1; i < nums.size(); i++){if(nums[i] > b) return true; else if(nums[i] > a) b = nums[i];else a = nums[i];}return false;}
};java算法代码：
class Solution
{public boolean increasingTriplet(int[] nums) {int a = nums[0], b = Integer.MAX_VALUE;for(int i = 1; i < nums.length; i++){if(nums[i] > b) return true;else if(nums[i] > a) b = nums[i];else a = nums[i];}return false;}
}