algo-aha

翻转成“先0后1的数”的minFlips

• https://leetcode.com/problems/flip-string-to-monotone-increasing/

可用动态规划

int minFlipsMonoIncr(string S) {
    // 设子问题S[0..i]以'0'结尾时minFlips为dp[i][0]，以'1'结尾时minFlips为dp[i][1]
    //  dp[i][0] = dp[i-1][0] + (S[i]=='1')
    //  dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + (S[i]=='0')
    // 递推式在i这维上只依赖i-1项，省掉i这维：
    //  dp[1] = min(dp[0], dp[1]) + (S[i]=='0')
    //  dp[0] += (S[i]=='1')  // dp[0]覆盖放后面
    int f0 = 0, f1 = 0;
    for (char c : S) {
        f1 = min(f0, f1) + (c == '0');
        f0 += (c == '1');
    }
    return min(f0, f1);
}

也可用前缀后缀数组

int minFlipsMonoIncr(string S) {
    const int N = S.size();
    vector<int> pre(N + 1); // pre[i]表示S[..i-1]以0结尾
    for (int i = 0; i < N; i++) {
        pre[i+1] = pre[i] + (S[i] == '1');
    }
    vector<int> suf(N + 1); // suf[i]表示S[i..]以1开头
    for (int i = N - 1; i >= 0; i--) {
        suf[i] = suf[i+1] + (S[i] == '0');
    }

    int ans = INT_MAX;
    for (int i = 0; i <= N; i++) {
        ans = min(ans, pre[i] + suf[i]);
    }
    return ans;
}

山峰数组

• https://leetcode.com/problems/longest-mountain-in-array/

int longestMountain(vector<int>& A) {
    const int N = A.size();
    vector<int> inc(N), dec(N);
    for (int i = 1; i < N; i++) {
        if (A[i] > A[i-1]) 
            inc[i] = inc[i-1] + 1;
    }
    for (int i = N - 2; i >= 0; i--) {
        if (A[i] > A[i+1]) 
            dec[i] = dec[i+1] + 1;
    }
    int ans = 0;
    for (int i = 1; i < N - 1; i++) {
        if (inc[i] && dec[i]) 
            ans = max(ans, inc[i] + dec[i] + 1);
    }
    return ans;
}

也可一遍扫描统计

int longestMountain(vector<int>& A) {
    // 统计一段上升和下降的最大长度
    int up = 0, down = 0, ans = 0;
    for (int i = 1; i < A.size(); i++) {
        if (A[i] > A[i-1]) {
            if (down > 0) up = down = 0; // 下降结束，开始新一段的统计
            up++;
        } else if (A[i] < A[i-1]) {
            down++;
        } else {
            up = down = 0; // 开始新一段的统计
        }
        
        if (up > 0 && down > 0) {
            ans = max(ans, 1 + up + down); // 1来自统计开始处的元素
        }
    }
    return ans;
}

各项为除了自己外的数组乘积

• https://leetcode.com/problems/product-of-array-except-self/

vector<int> productExceptSelf(vector<int>& nums) {
    const int N = nums.size();
    vector<int> ans(N, 1);
    // 从左到右扫一遍
    for (int i = 0, prodL = 1; i < N; i++) {
        ans[i] *= prodL;
        prodL *= nums[i];
    }
    // 从右到左扫一遍
    for (int i = N - 1, prodR = 1; i >= 0; i--) {
        ans[i] *= prodR;
        prodR *= nums[i];
    }
    return ans;
}