文章目錄

• 題目描述
• 思路 & 代碼
• • • 動態規劃 O($n^2$)
    • 動態規劃 + 二分法 + 貪心 O($nlogn$)
    • 二刷

題目描述

• 難點在于時間復雜度 O(n * logn）的做法
  
  

思路 & 代碼

動態規劃 O($n^2$)

• 先拋磚引玉啦～
• dp[i]：以 nums[i] 結尾的子序列，能達到的最大長度
• 對于 dp[i] 來說，只要找到前面的比 nums[i] 小的 nums[j] 中最大的 dp[j] 即可

class Solution {public int lengthOfLIS(int[] nums) {int len = nums.length;int ans = 1;// dp[i]：以 nums[i] 結尾的子序列，能達到的最長長度int[] dp = new int[len];// 邊界dp[0] = 1;// 復雜度 O(n^2)for(int i = 1; i < len; i++){// 找到前面結點里，比 nums[i] 小的中，dp[] 最長的值int maxPre = 0;for(int j = i - 1; j >= 0; j--){if(nums[i] > nums[j]){// dp[j] 最優子結構maxPre = Math.max(dp[j], maxPre);}}// 狀態轉移方程dp[i] = maxPre + 1;ans = Math.max(ans, dp[i]);}return ans;} }

動態規劃 + 二分法 + 貪心 O($nlogn$)

• 新定義 tail[i]：代表長度為 i + 1 的遞增子序列的最小尾值
• 詳見注釋。建議還是看看這篇題解，結合里面的動圖會更好地理解這道題。

class Solution {public int lengthOfLIS(int[] nums) {// dp + 二分 + 貪心int len = nums.length;// tail[i]：長度為 i + 1 的遞增子序列的最小尾值int[] tail = new int[len];// 邊界tail[0] = nums[0];// 尾值下標int endIndex = 0;for(int i = 1; i < len; i++){// nums[i] > tail[endIndex] 的情況：加入尾，更新 endIndexif(nums[i] > tail[endIndex]){tail[++endIndex] = nums[i];}// <= 的情況，二分法找到第一個 >= nums[i] 的值，并更新else{int left = 0, right = endIndex;// 區間選擇：[left, mid] [mid + 1, right]while(left < right){// mid 向下取整，防止 mid == right 的情況導致死循環int mid = left + (right - left) / 2;// 直接舍棄掉這部分，mid 是用不到的if(tail[mid] < nums[i]){left = mid + 1;}// mid 是可能用得到的else{right = mid;}}// 更新所取值tail[left] = nums[i];}}// 由下標獲取長度int ans = endIndex + 1;return ans;} } /*** Q：為什么可以直接更新到前方？比如 [2,3,8,18]遇到4，更新成[2,3,4,18]* 1. 這個數組在 endIndex 不變的維護過程中，只有[0, left]是滿足題目條件的序列，[left + 1, endIndex]則不保證* 2. 但是在 endIndex 增加的維護過程，可以保證“正確性”：因為之前肯定出現過滿足題目條件的[0, endIndex]的，* 1.的維護過程是建立于此的基礎上進行更新的，因此 endIndex 值的正確性是可以保證的。* 3. 小值更新到前方：貪心，這是為了之后遇到較小值也可以增加 endIndex 而服務的 */

二刷

• 寫不出 O(logN) 的，我還寫不出你 O(n^2) 的嗎！
• 10+ 行代碼，還是挺清晰的，記得 dp[nums.length - 1] 不一定是最終答案噢～

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];dp[0] = 1;int res = 1;for(int i = 1; i < nums.length; i++) {int max = 0;for(int j = 0; j < i; j++) {if(nums[j] < nums[i]) {max = Math.max(max, dp[j]);}}dp[i] = max + 1;res = Math.max(res, dp[i]);}return res;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】300. 最长递增子序列（Java、动态规划、二分法、贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。