975.奇偶跳

 

//二分搜索 

O(nlogn)  O(n)

int oddEvenJumps(vector<int>& A) {const int n=A.size();vector<vector<int> > dp(n,vector<int>(2));dp[n-1][0]=dp[n-1][1]=1;map<int,int> mp; //<value,index>  BSTmp[A[n-1]]=n-1;int ans=1;for(int i=n-2;i>=0;i--){auto o=mp.lower_bound(A[i]);   //>=  up jumpif(o!=mp.end()) dp[i][0]=dp[o->second][1];auto e=mp.upper_bound(A[i]);  //>  down jumpif(e!=mp.begin()) dp[i][1]=dp[prev(e)->second][0];    //<=  prev(e) 返回e的前一个迭代器if(dp[i][0]) ++ans;mp[A[i]]=i;}return ans;
}