牛客NC164 最长上升子序列(二)【困难贪心+二分 Java/Go/PHP/C++】

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237

思路

贪心+二分

    所谓贪心，就是往死里贪，所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，
    也就可能变得更长
    所以贪心的做法是，建立一个dp数组,dp[i[表示长度为i的LIS结尾元素的最小值，
    因此我们只需要维护dp数组即可

    对于每一个数组的数，我们对他们进行判断，如果他大于等于dp[ans]的值，就把他放在数组后面，
    dp[++ans] = tr[i]，
    否则，就在dp中去找大一个大于等于他的位置pos，dp[pos] = tr[i]。如果从头扫一遍数组，
    时间复杂度还是O（n^2），
    这与曹贼何异？！通过观察我们知道，这次维护的dp数组是单调递增的，
    所以就可以使出秘技二分之lower_bound来找pos的位置
    我们举个栗子：

        tr[] = 2 5 18 3 4 7 10 9 11 8 15
        dp[1] = 2;
        5大于2，所以dp[2] = 5
        18大于5，所以dp[3] = 18
        3小于18，所以二分去找，pos是2，所以dp[2] = 3
        4小于18，所以二分去找，pos是3，所以dp[3] = 4
        7大于4，所以dp[4] = 7
        10大于7，所以dp[5] = 10
        9小于10，所以二分去找，pos是5，dp[5] = 9
        11大于9，所以dp[6] = 11
        8小于11，所以二分去找，pos是5，dp[5] = 8
        15大于11，所以dp[7] = 15

    所以最长上升子序列的长度为7
    注意：dp数组得到的不一定是真正的LIS
    比如：tr[] = 1 4 7 2 5 9 10 3
    得到的是1 2 3 9 10，而真正的LIS是1 2 5 9 10
    因此dp数组得到的不一定是真正的LIS，他只表示最长子序列长度的排好序的最小序列，
    对于最后一半将5换成3的意义是记录最小序列，便于后续数据的处理

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] a) {
        //https://blog.csdn.net/weixin_51216553/article/details/114678534
        /*
        贪心+二分

        所谓贪心，就是往死里贪，所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，也就可能变得更长
        所以贪心的做法是，建立一个dp数组,dp[i[表示长度为i的LIS结尾元素的最小值，因此我们只需要维护dp数组即可

        对于每一个数组的数，我们对他们进行判断，如果他大于等于dp[ans]的值，就把他放在数组后面，dp[++ans] = tr[i]，
        否则，就在dp中去找大一个大于等于他的位置pos，dp[pos] = tr[i]。如果从头扫一遍数组，时间复杂度还是O（n^2），
        这与曹贼何异？！通过观察我们知道，这次维护的dp数组是单调递增的，所以就可以使出秘技二分之lower_bound来找pos的位置
        我们举个栗子：

            tr[] = 2 5 18 3 4 7 10 9 11 8 15
            dp[1] = 2;
            5大于2，所以dp[2] = 5
            18大于5，所以dp[3] = 18
            3小于18，所以二分去找，pos是2，所以dp[2] = 3
            4小于18，所以二分去找，pos是3，所以dp[3] = 4
            7大于4，所以dp[4] = 7
            10大于7，所以dp[5] = 10
            9小于10，所以二分去找，pos是5，dp[5] = 9
            11大于9，所以dp[6] = 11
            8小于11，所以二分去找，pos是5，dp[5] = 8
            15大于11，所以dp[7] = 15

        所以最长上升子序列的长度为7
        注意：dp数组得到的不一定是真正的LIS
        比如：tr[] = 1 4 7 2 5 9 10 3
        得到的是1 2 3 9 10，而真正的LIS是1 2 5 9 10
        因此dp数组得到的不一定是真正的LIS，他只表示最长子序列长度的排好序的最小序列，对于最后一半将5换成3的意义是记录最小序列，便于后续数据的处理
         */
        int n = a.length;
        if (n <= 1) return n;

        int[] dp = new int[n + 1];
        int idx = 1;
        dp[idx] = a[0];
        // 利用贪心 + 二分查找进行更新
        for (int i = 1; i < n ; i++) {
            if (dp[idx] < a[i]) {
                idx++;
                dp[idx] = a[i];
            } else {
                int l = 1;
                int r = idx;
                int pos = 0;

                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (dp[mid] < a[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                dp[pos + 1] = a[i];
            }
        }
        return idx;
    }
}

Go代码

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 该数组最长严格上升子序列的长度
 * @param a int整型一维数组 给定的数组
 * @return int整型
 */
func LIS(a []int) int {
	//https://blog.csdn.net/weixin_51216553/article/details/114678534
	/*
	   贪心+二分

	   所谓贪心，就是往死里贪，所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，也就可能变得更长
	   所以贪心的做法是，建立一个dp数组,dp[i[表示长度为i的LIS结尾元素的最小值，因此我们只需要维护dp数组即可

	   对于每一个数组的数，我们对他们进行判断，如果他大于等于dp[ans]的值，就把他放在数组后面，dp[++ans] = tr[i]，
	   否则，就在dp中去找大一个大于等于他的位置pos，dp[pos] = tr[i]。如果从头扫一遍数组，时间复杂度还是O（n^2），
	   这与曹贼何异？！通过观察我们知道，这次维护的dp数组是单调递增的，所以就可以使出秘技二分之lower_bound来找pos的位置
	   我们举个栗子：

	       tr[] = 2 5 18 3 4 7 10 9 11 8 15
	       dp[1] = 2;
	       5大于2，所以dp[2] = 5
	       18大于5，所以dp[3] = 18
	       3小于18，所以二分去找，pos是2，所以dp[2] = 3
	       4小于18，所以二分去找，pos是3，所以dp[3] = 4
	       7大于4，所以dp[4] = 7
	       10大于7，所以dp[5] = 10
	       9小于10，所以二分去找，pos是5，dp[5] = 9
	       11大于9，所以dp[6] = 11
	       8小于11，所以二分去找，pos是5，dp[5] = 8
	       15大于11，所以dp[7] = 15

	   所以最长上升子序列的长度为7
	   注意：dp数组得到的不一定是真正的LIS
	   比如：tr[] = 1 4 7 2 5 9 10 3
	   得到的是1 2 3 9 10，而真正的LIS是1 2 5 9 10
	   因此dp数组得到的不一定是真正的LIS，他只表示最长子序列长度的排好序的最小序列，对于最后一半将5换成3的意义是记录最小序列，便于后续数据的处理
	*/
	n := len(a)
	if n <= 1 {
		return n
	}

	dp := make([]int, n+1)
	idx := 1
	dp[idx] = a[0]

	//利用贪心+二分查找进行更新
	for i := 1; i < n; i++ {
		if dp[idx] < a[i] {
			idx++
			dp[idx] = a[i]
		} else {
			l := 1
			r := idx
			pos := 0
			for l <= r {
				mid := (l + r) >> 1
				if dp[mid] < a[i] {
					pos = mid
					l = mid + 1
				} else {
					r = mid - 1
				}
			}
			dp[pos+1] = a[i]
		}
	}

	return idx
}

PHP代码

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 该数组最长严格上升子序列的长度
 * @param a int整型一维数组 给定的数组
 * @return int整型
 */
function LIS( $a )
{
      //https://blog.csdn.net/weixin_51216553/article/details/114678534
    /*
       贪心+二分

       所谓贪心，就是往死里贪，所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，也就可能变得更长
       所以贪心的做法是，建立一个dp数组,dp[i[表示长度为i的LIS结尾元素的最小值，因此我们只需要维护dp数组即可

       对于每一个数组的数，我们对他们进行判断，如果他大于等于dp[ans]的值，就把他放在数组后面，dp[++ans] = tr[i]，
       否则，就在dp中去找大一个大于等于他的位置pos，dp[pos] = tr[i]。如果从头扫一遍数组，时间复杂度还是O（n^2），
       这与曹贼何异？！通过观察我们知道，这次维护的dp数组是单调递增的，所以就可以使出秘技二分之lower_bound来找pos的位置
       我们举个栗子：

           tr[] = 2 5 18 3 4 7 10 9 11 8 15
           dp[1] = 2;
           5大于2，所以dp[2] = 5
           18大于5，所以dp[3] = 18
           3小于18，所以二分去找，pos是2，所以dp[2] = 3
           4小于18，所以二分去找，pos是3，所以dp[3] = 4
           7大于4，所以dp[4] = 7
           10大于7，所以dp[5] = 10
           9小于10，所以二分去找，pos是5，dp[5] = 9
           11大于9，所以dp[6] = 11
           8小于11，所以二分去找，pos是5，dp[5] = 8
           15大于11，所以dp[7] = 15

       所以最长上升子序列的长度为7
       注意：dp数组得到的不一定是真正的LIS
       比如：tr[] = 1 4 7 2 5 9 10 3
       得到的是1 2 3 9 10，而真正的LIS是1 2 5 9 10
       因此dp数组得到的不一定是真正的LIS，他只表示最长子序列长度的排好序的最小序列，对于最后一半将5换成3的意义是记录最小序列，便于后续数据的处理
    */
     $n = count($a);
    if($n<=1){
        return $n;
    }

    $dp =[0];
    $idx = 1;
    $dp[$idx] = $a[0];

    // 利用贪心 + 二分查找进行更新
    for($i=1;$i<$n;$i++){
        if($dp[$idx] <$a[$i]){
            $idx++;
            $dp[$idx] = $a[$i];
        }else{
            $l=1;
            $r =$idx;
            $pos=0;
            while ($l<=$r){
                $mid = ($l+$r) >>1;
                if($dp[$mid] <$a[$i]){
                    $pos = $mid;
                    $l=$mid+1;
                }else{
                    $r = $mid-1;
                }
            }

            $dp[$pos+1] = $a[$i];
        }
    }
    return $idx;
}

C++代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& a) {
        //https://blog.csdn.net/weixin_51216553/article/details/114678534
        /*
        贪心+二分

        所谓贪心，就是往死里贪，所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，也就可能变得更长
        所以贪心的做法是，建立一个dp数组,dp[i[表示长度为i的LIS结尾元素的最小值，因此我们只需要维护dp数组即可

        对于每一个数组的数，我们对他们进行判断，如果他大于等于dp[ans]的值，就把他放在数组后面，dp[++ans] = tr[i]，
        否则，就在dp中去找大一个大于等于他的位置pos，dp[pos] = tr[i]。如果从头扫一遍数组，时间复杂度还是O（n^2），
        这与曹贼何异？！通过观察我们知道，这次维护的dp数组是单调递增的，所以就可以使出秘技二分之lower_bound来找pos的位置
        我们举个栗子：

            tr[] = 2 5 18 3 4 7 10 9 11 8 15
            dp[1] = 2;
            5大于2，所以dp[2] = 5
            18大于5，所以dp[3] = 18
            3小于18，所以二分去找，pos是2，所以dp[2] = 3
            4小于18，所以二分去找，pos是3，所以dp[3] = 4
            7大于4，所以dp[4] = 7
            10大于7，所以dp[5] = 10
            9小于10，所以二分去找，pos是5，dp[5] = 9
            11大于9，所以dp[6] = 11
            8小于11，所以二分去找，pos是5，dp[5] = 8
            15大于11，所以dp[7] = 15

        所以最长上升子序列的长度为7
        注意：dp数组得到的不一定是真正的LIS
        比如：tr[] = 1 4 7 2 5 9 10 3
        得到的是1 2 3 9 10，而真正的LIS是1 2 5 9 10
        因此dp数组得到的不一定是真正的LIS，他只表示最长子序列长度的排好序的最小序列，对于最后一半将5换成3的意义是记录最小序列，便于后续数据的处理
         */
        int n = a.size();
        if (n <= 1) {
            return n;
        }

        vector<int> dp(n + 1, 0);
        int idx = 1;
        dp[idx] = a[0];
        // 利用贪心 + 二分查找进行更新
        for (int i = 1; i < n; i++) {
            if (dp[idx] < a[i]) {
                dp[++idx] = a[i];
            } else {
                int l = 1;
                int r = idx;
                int pos = 0;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (dp[mid] < a[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                dp[pos + 1] = a[i];
            }
        }
        return idx;
    }
};