01.最長遞增子序列

題目鏈接：https://leetcode.cn/problems/longest-increasing-subsequence/

給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度。

子序列 是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [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

思路

可以通過維護(hù)一個(gè)數(shù)組，其中 ret[i] 表示長度為 i+1 的遞增子序列中，最后一個(gè)元素的最小值。在遍歷數(shù)組過程中，不斷更新這個(gè)數(shù)組，以確保它仍然滿足遞增的性質(zhì)。

每當(dāng)新元素加入時(shí)，可以利用二分查找找到當(dāng)前元素在 ret 數(shù)組中的插入位置，然后更新這個(gè)位置上的值。這樣，就能夠在數(shù)組中維護(hù)遞增子序列的信息。

這種方法的關(guān)鍵點(diǎn)在于，我們只關(guān)心遞增子序列的最后一個(gè)元素，而不是整個(gè)遞增子序列的具體形狀。通過維護(hù)最后一個(gè)元素的最小值，可以在遍歷數(shù)組時(shí)保持遞增子序列的長度信息，并在需要時(shí)更新。

代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-841494.html

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/

給你一個(gè)整數(shù)數(shù)組 nums ，判斷這個(gè)數(shù)組中是否存在長度為 3 的遞增子序列。

如果存在這樣的三元組下標(biāo) (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) 滿足題意，因?yàn)?nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

思路

上一題的精簡版，可以直接用上面的代碼返回長度是否大于等于三即可，但在這里我們不需要這么復(fù)雜，僅需連個(gè)變量即可。

代碼

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.最長連續(xù)遞增序列

題目鏈接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組，找到最長且 連續(xù)遞增的子序列，并返回該序列的長度。

連續(xù)遞增的子序列 可以由兩個(gè)下標(biāo) l 和 r（l < r）確定，如果對(duì)于每個(gè) l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續(xù)遞增子序列。

示例 1：

輸入：nums = [1,3,5,4,7]
輸出：3
解釋：最長連續(xù)遞增序列是 [1,3,5], 長度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因?yàn)?5 和 7 在原數(shù)組里被 4 隔開。 

示例 2：

輸入：nums = [2,2,2,2,2]
輸出：1
解釋：最長連續(xù)遞增序列是 [2], 長度為1。 

提示：

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

思路

當(dāng)找到以某個(gè)位置為起點(diǎn)的最長連續(xù)遞增序列后，可以直接將下一個(gè)位置作為新的起點(diǎn)，繼續(xù)尋找下一個(gè)最長連續(xù)遞增序列。

代碼

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.買賣股票的最佳時(shí)機(jī)

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

給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

示例 1：

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格；同時(shí)，你不能在買入前賣出股票。

示例 2：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。

提示：

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

思路

遍歷數(shù)組，在每個(gè)位置 i 處計(jì)算當(dāng)前價(jià)格與之前最低價(jià)格的差值，更新最大利潤。在遍歷過程中，始終保持記錄前面最低價(jià)格的變量。當(dāng)找到更低的價(jià)格時(shí)，更新這個(gè)變量；當(dāng)計(jì)算當(dāng)前位置的利潤時(shí)，與之前記錄的最大利潤進(jìn)行比較，如果更大則更新最大利潤。

代碼

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;
    }
};

到了這里，關(guān)于算法沉淀——貪心算法二（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！