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中文网其他相关文章！