feat: solve No.300

BaffinLee · BaffinLee · commit edf24b46d574 · 2024-01-06T23:59:52.000+08:00
diff --git a/201-300/300. Longest Increasing Subsequence.md b/201-300/300. Longest Increasing Subsequence.md
@@ -0,0 +1,92 @@
+# 300. Longest Increasing Subsequence
+
+- Difficulty: Medium.
+- Related Topics: Array, Binary Search, Dynamic Programming.
+- Similar Questions: Increasing Triplet Subsequence, Russian Doll Envelopes, Maximum Length of Pair Chain, Number of Longest Increasing Subsequence, Minimum ASCII Delete Sum for Two Strings, Minimum Number of Removals to Make Mountain Array, Find the Longest Valid Obstacle Course at Each Position, Minimum Operations to Make the Array K-Increasing, Longest Ideal Subsequence, Maximum Number of Books You Can Take, Longest Increasing Subsequence II.
+
+## Problem
+
+Given an integer array `nums`, return **the length of the longest **strictly increasing ********subsequence****.
+
+ 
+Example 1:
+
+```
+Input: nums = [10,9,2,5,3,7,101,18]
+Output: 4
+Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
+```
+
+Example 2:
+
+```
+Input: nums = [0,1,0,3,2,3]
+Output: 4
+```
+
+Example 3:
+
+```
+Input: nums = [7,7,7,7,7,7,7]
+Output: 1
+```
+
+ 
+**Constraints:**
+
+
+	
+- `1 <= nums.length <= 2500`
+	
+- `-104 <= nums[i] <= 104`
+
+
+ 
+**Follow up:** Can you come up with an algorithm that runs in `O(n log(n))` time complexity?
+
+
+## Solution
+
+```javascript
+/**
+ * @param {number[]} nums
+ * @return {number}
+ */
+var lengthOfLIS = function(nums) {
+    var arr = [nums[0]];
+    for (var i = 1; i < nums.length; i++) {
+        if (nums[i] > arr[arr.length - 1]) {
+            arr.push(nums[i]);
+        } else {
+            var index = binarySearch(arr, nums[i]);
+            arr[index] = nums[i];
+        }
+    }
+    return arr.length;
+};
+
+var binarySearch = function(arr, num) {
+    var left = 0;
+    var right = arr.length - 1;
+    while (left < right) {
+        var mid = left + Math.floor((right - left) / 2);
+        if (arr[mid] > num) {
+            right = mid;
+        } else if (arr[mid] === num) {
+            return mid;
+        } else {
+            left = mid + 1;
+        }
+    }
+    return left;
+};
+```
+
+**Explain:**
+
+nope.
+
+**Complexity:**
+
+* Time complexity : O(n * log(n)).
+* Space complexity : O(n).
