C++ solution with binary search


  • 0
    V

    passed all tests, but not convinced my answer is 100% correct. Any suggestion is greatly appreciated.

    public:
      int lengthOfLIS(vector<int>& nums) {
        if (!nums.size()) return 0;
        vector<int> res;
        res.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++) {
          if (nums[i] > res[res.size()-1]) {
            res.push_back(nums[i]);
          }
          else {
            searchAndInsert(res, nums[i]);
          }
        }
        return res.size();
      }
    
      void searchAndInsert(vector<int> &res, int target) {
        int start = 0;
        int end = res.size()-1;
        int candidate = 0;
        while (start <= end) {
          int mid = (start + end) / 2;
          if (target < res[mid]) {
            candidate = mid;
            end = mid-1;
          }
          else if (target > res[mid]) {
            start = mid+1;
          }
          else return;
        }
        res[candidate] = target;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.