LeetCode-300 最長上升子序列

• 2020 年 3 月 14 日
• 筆記

LeetCode_300 最長上升子序列

description:

給定一個無序的整數數組nums，找到其中最長上升子序列的長度。

示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
說明:

可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可。
你算法的時間複雜度應該為 O(n2) 。
進階: 你能將算法的時間複雜度降低到 O(n log n) 嗎?

思路：

思路一：直接粗暴，O(n^2)動態規劃

這個思路比較簡單粗暴，定義dp[i]為以[0,i]為區間的，且以nums[i]為尾的最長上升子序列的值。循環遍曆數組nums,當遍歷到nums[i]時，dp[0]~dp[i-1]都已經算出來了。
那麼狀態轉移方程為：

    dp[i] = max(dp[j])+1;其中  0<=j<=i-1;

代碼：

class Solution {  public:      int lengthOfLIS(vector<int>& nums) {          int n = nums.size();          if(!n)              return 0;          int dp[n];          int ans = 1;          for(int i=0;i<nums.size();i++){              dp[i] = 1;              for(int j=0;j<i;j++){                  if(nums[i]>nums[j]){                      dp[i] = max(dp[i],dp[j]+1);                      ans = max(ans,dp[i]);                  }              }              ans = max(ans,dp[i]);          }          return ans;        }  };

複雜度分析：

時間複雜度：O(n^2)，雙層遍歷

空間複雜度：O(n)，需要一個dp數組

思路二：二分+貪心

這個思路比較tricky，不容易想到。
維護一個數組dp，dp[i]表示以i+1為最長上升子序列的最後一個元素，可以證明dp數組是嚴格遞增的。
遍歷nums，然後去dp中尋找第一個比nums大的數（這裡用到二分查找，查找floor），然後替換它；如果nums>dp.back()，直接將nums添加到dp的末尾；

class Solution {  public:      int lengthOfLIS(vector<int>& nums) {          int n = nums.size();          if(!n)              return 0;          vector<int> dp;          dp.push_back(nums[0]);          for(int i=1;i<n;i++){              if(nums[i]>dp.back()){                  dp.push_back(nums[i]);              }else{                  int l = 0;                  int r = dp.size()-1;                  while(l<r){                      int mid = l + (r-l)/2;                      if(dp[mid]<nums[i]){                          l = mid+1;                      }else{                          r = mid;                      }                  }                  dp[l] = nums[i];              }          }          return dp.size();      }  };