算法沉淀——贪心算法二（leetcode真题剖析）

算法沉淀——贪心算法二

• 01.最长递增子序列
• 02.递增的三元子序列
• 03.最长连续递增序列
• 04.买卖股票的最佳时机

01.最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/

给你一个整数数组 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
• -104 <= nums[i] <= 104

思路

可以通过维护一个数组，其中 ret[i] 表示长度为 i+1 的递增子序列中，最后一个元素的最小值。在遍历数组过程中，不断更新这个数组，以确保它仍然满足递增的性质。

每当新元素加入时，可以利用二分查找找到当前元素在 ret 数组中的插入位置，然后更新这个位置上的值。这样，就能够在数组中维护递增子序列的信息。

这种方法的关键点在于，我们只关心递增子序列的最后一个元素，而不是整个递增子序列的具体形状。通过维护最后一个元素的最小值，可以在遍历数组时保持递增子序列的长度信息，并在需要时更新。

代码

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];
            }
        }
        return ret.size();
    }
};

02.递增的三元子序列

题目链接：https://leetcode.cn/problems/increasing-triplet-subsequence/

给你一个整数数组 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 * 105
• -231 <= nums[i] <= 231 - 1

思路

上一题的精简版，可以直接用上面的代码返回长度是否大于等于三即可，但在这里我们不需要这么复杂，仅需连个变量即可。

代码

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n=nums.size();
        int a=nums[0],b=INT_MAX;
        for(int i=1;i<n;i++){
            if(nums[i]>b) return true;
            else if(nums[i]>a) b=nums[i];
            else a=nums[i];
        }
        return false;
    }
};

03.最长连续递增序列

题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。 

提示：

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

思路

当找到以某个位置为起点的最长连续递增序列后，可以直接将下一个位置作为新的起点，继续寻找下一个最长连续递增序列。

代码

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

04.买卖股票的最佳时机

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

思路

遍历数组，在每个位置 i 处计算当前价格与之前最低价格的差值，更新最大利润。在遍历过程中，始终保持记录前面最低价格的变量。当找到更低的价格时，更新这个变量；当计算当前位置的利润时，与之前记录的最大利润进行比较，如果更大则更新最大利润。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret=0,n=prices.size();
        for(int i=0,prevMin=INT_MAX;i<n;i++){
            ret=max(ret,prices[i]-prevMin);
            prevMin=min(prevMin,prices[i]);
        }
        return ret;
    }
};