LeetCode 926. 将字符串翻转到单调递增*

值得注意的是这个题目的LCS思路；

可以转化为寻找一个序列的最长不下降子串，之后直接总长度-1，但是这样必定是 n 2 n^2 n2的复杂度；

可以转为LIS问题；

使用dp数组g，下标表示长度为i的序列，内容为长度为i的序列结尾元素为多少；

通过二分可以将时间变为 n l o g n nlogn nlogn；

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n=s.size();
        vector> dp(n,vector(2,INT_MAX));
        if(s[0]=='0'){
            dp[0][1]=1;
            dp[0][0]=0;
        }else{
            dp[0][0]=1;
            dp[0][1]=0;
        }
        for(int i=1;i
            if(s[i]=='0'){
                dp[i][0]=dp[i-1][0];
                dp[i][1]=min(dp[i-1][1],dp[i-1][0])+1;
            }else{
                dp[i][0]=dp[i-1][0]+1;//0 TAIL
                dp[i][1]=min(dp[i-1][0],dp[i-1][1]);//1 tail
            }
        }
        return min(dp[n-1][1],dp[n-1][0]);
    }
};

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n=s.size();
        vectorg(n+1,0);
        int ans=0;
        for (int i = 0; i < n; i++) {
            int t = s[i] - '0';
            int l = 1, r = ans + 1;
            while (l < r) {
                int mid = l+(r-l)/2;
                if (g[mid] > t) 
                    r = mid;
                else 
                    l = mid + 1;
            }
            g[r] = t;
            ans =max(ans, r);
        }
        return n-ans;
    }
};

//3 2 5 2 1 0