LeetCode Day 動態規劃 第 10 部分

300.最長遞增子序列

給定一個整數數組 nums，傳回最長嚴格遞增的長度
子序列
.

範例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 -10^4

跟進：你能想出一個以 O(n log(n)) 時間複雜度運行的演算法嗎？
原始頁

錯誤代碼

    public int lengthOfLIS(int[] nums) {
        int start = nums[0];
        int pre = nums[0];
        int preMax = nums[0];
        int cnt = 1;
        int max = 1;

        for(int i=1; i<nums.length; i++){
            if(nums[i] < start){
                max = Math.max(max, cnt);
                start = nums[i];
                cnt = 1;
            } 
            else if(nums[i] > pre){
                cnt ++;
            }
            pre = nums[i];
            System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt);
        }
        return Math.max(max, cnt);
    }

修復錯誤

向他人學習樹形圖

    public int lengthOfLIS(int[] nums) {


        TreeMap<Integer,Integer> map = new TreeMap<>();

        map.put(Integer.MIN_VALUE,0);

       for(int i: nums)
       {
           map.put(i,map.get(map.lowerKey(i))+1);
           while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i)) 
           {
            map.remove(map.higherKey(i));
           }
       }

       return map.get(map.lastKey());

    }

---

674. 最長連續遞增子序列

給定一個未排序的整數數組 nums，傳回最長連續遞增子序列（即子數組）的長度。子序列必須嚴格遞增。

連續遞增子序列由兩個索引l 和r (l < r) 定義，因此它是[nums[l], nums[l + 1], ..., nums[r - 1], nums [ r]] 並且對每個l <= i < r, nums[i] < nums[i + 1].

範例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 <= 10^4
-10^9 <= nums[i] <= 10^9
原始頁

貪心演算法

    public int findLengthOfLCIS(int[] nums) {
        if(nums.length < 1){
            return 0;
        }
        int res = 1;
        int cnt = 1;
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i] > pre){
                cnt++;
            }else{
                res = Math.max(res, cnt);
                cnt = 1;
            }
            // System.out.println("cur: " + nums[i] + " pre:" + pre + " count:" + cnt);
            pre = nums[i];
        }
        return Math.max(res, cnt);
    }

動態規劃

與上一題不同的是，本題我們只能考慮不斷增加子序列，簡化了流程。

以上是LeetCode Day 動態規劃 第 10 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！