public int findLengthOfLCIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int maxLength = 1; // 最长连续递增子序列的长度至少为1
    int currentLength = 1; // 当前连续递增子序列的长度

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) { // 如果当前元素大于前一个元素
            currentLength++; // 增加当前连续递增子序列的长度
            maxLength = Math.max(maxLength, currentLength); // 更新最大长度
        } else {
            currentLength = 1; // 重置当前连续递增子序列的长度
        }
    }

    return maxLength; // 返回最长连续递增子序列的长度
}

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

/*双指针逆序处理，时间复杂度来为O(m+n)，空间复杂度为O(1)*/
public static void mergeFastLessSpace(int[] nums1, int m, int[] nums2, int n) {
    int k = m+n;
    for(int index = k-1,nums1Index = m-1,nums2Index = n-1;
        index >= 0;
        index--){
        if(nums1Index < 0){/*nums1已经取完，完全取nums2的值即可*/
            nums1[index] = nums2[nums2Index--];
        }else if(nums2Index < 0){/*nums2已经取完，完全取nums1的值即可*/
            break;
        }else  if(nums1[nums1Index] > nums2[nums2Index]){/*nums1的元素值大于nums2，取nums1值*/
            nums1[index] = nums1[nums1Index--];
        }else{/*nums2的元素值大于等于nums1，取nums2的值*/
            nums1[index] = nums2[nums2Index--];
        }
    }
}

public static boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        if (!set.add(head)) {
            return true; // 如果添加失败，说明已经存在该节点，即存在环
        }
        head = head.next;
    }
    return false; // 遍历完整个链表，没有发现重复节点，说明不存在环
}

public static int fibonacci(int n) {
   if (n == 0) {
       return 0;
   }
   if (n == 1) {
       return 1;
   }
   return fibonacci(n - 1) + fibonacci(n - 2);
}

public static int sort (int[] nums){
    Arrays.sort(nums); // O(n log n)
    int n = nums.length;
    return Math.max(nums[0] * nums[1] * nums[n-1], nums[n-1] * nums[n-2] * nums[n-3]);
}

public ListNode reverseList(ListNode head) {
    ListNode preNode = null;
    ListNode currNode = head;
    while(currNode != null){
        /*因为下面要把currNode的next改为指向preNode
        * 为了不丢失本来的结点指向，所以所以需要事先保存一下*/
        ListNode next = currNode.next;
        currNode.next = preNode;
        /*移动双指针*/
        preNode = currNode;
        currNode = next;
    }
    return preNode;
}

public class sqrt {
    public static void main(String[] args) {
        System.out.println(binarySearch(24)); //4
        System.out.println(newton(24)); //4
    }

    public static int binarySearch(int x){
        int index = -1;
        int left = 0, right = x;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(mid * mid <= x){
                index = mid;
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
        return index;
    }

    public static int newton(int x) {
        if (x == 0) return 0;
        return (int) sqrt1(x,x);
    }

    public static double sqrt1(double i, int x) {
        double res = (i+ x/i)/2;
        if(res == i){
            return i;
        } else {
            return sqrt1(res, x);
        }
    }
}