1.最短且字典序最小的美丽子字符串

滑动窗口

string shortestBeautifulSubstring(string s, int k) {
    if(count(s.begin(),s.end(),'1')<k)  return "";
    int cnt=0,left=0;
    string ans=s;
    for(int right=0;right<s.length();right++){
        cnt+=s[right]-'0';
        while(cnt>k||s[left]=='0'){
            cnt-=s[left++]-'0';
        }
        if(cnt==k){
            auto t=s.substr(left,right-left+1);
            if(ans.size()>t.size()||ans.size()==t.size()&&ans>t){
                ans=t;
            }
        }
    }   
    return ans;
}

2.找出满足差值条件的下标 II

维护最大最小

维护[0,i]的最大最小值下标

vector<int> findIndices(vector<int> &nums, int indexDifference, int valueDifference) {
    int max_idx=0,min_idx=0;
    for (int j=indexDifference; j < nums.size(); j++) {
        int i=j-indexDifference;
        if (nums[i] > nums[max_idx]) max_idx = i;
        else if (nums[i] < nums[min_idx])     min_idx = i;

        if (nums[max_idx] - nums[j] >= valueDifference)
            return {max_idx, j};
        if (nums[j] - nums[min_idx] >= valueDifference) 
            return {min_idx, j};
    }
    return {-1,-1};
}

3.构造乘积矩阵

维护前后缀乘积

const int mod=12345;
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid){
    long long pre=1,suf=1;
    int n=grid.size(),m=grid[0].size();
    vector<vector<int>> result(n,vector<int>(m));
    for(int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            result[i][j]=suf;
            suf=suf*grid[i][j]%mod;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            result[i][j]=result[i][j]*pre%mod;
            pre=pre*grid[i][j]%mod;
        }
    }
    return result;
}