1.最长的严格递增或递减子数组

    int longestMonotonicSubarray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,1),dp2(n,1);
        for(int i=1;i<n;i++){
            if(nums[i-1]<nums[i])
                dp[i]=dp[i-1]+1;
            if(nums[i-1]>nums[i])
                dp2[i]=dp2[i-1]+1;
        }

        return max(*max_element(dp.begin(),dp.end()),*max_element(dp2.begin(),dp2.end()));
    }

2.满足距离约束且字典序最小的字符串

class Solution {
public:
    int d(char a,char b){
        int t=abs(a-b);
        return min(t,26-t);
    }
    string getSmallestString(string s, int k) {
        int n=s.size();
        for(int i=0;i<n;i++){
            if(k==0) break;
            for(char c='a';c<='z';c++){
                int tmp=d(c,s[i]);
                if(tmp<=k){
                    k-=tmp;
                    s[i]=c;
                    break;
                }
            }
        }
        return s;
    }
};

    string getSmallestString(string s, int k) {
        for(auto &c:s){
            int tmp=min(c-'a','z'-c+1);
            if(tmp>=k)  {c-=k;break;}
            c='a';k-=tmp;
        }
        return s;
    }

3.使数组中位数等于 K 的最少操作数

    long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
        //使（n+1)/2个元素小于等于nums的最小操作数
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int idx=n/2;
        long long res=0;
        if(nums[idx]!=k){
            res+=abs(1LL*nums[idx]-k);
            nums[idx]=k;
        }
        for(int i=0;i<idx;i++){
            if(nums[i]>k){
                res+=abs(1LL*nums[i]-k);
            }
        }
        
        for(int i=idx+1;i<n;i++){
            if(nums[i]<k){
                res+=abs(1LL*nums[i]-k);
            }
        }
        return res;
    }

    long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
        //使（n+1)/2个元素小于等于nums的最小操作数
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int idx=n/2;
        long long res=0;
        if(nums[idx]>k){
            for(int i=0;i<=idx;i++){
                if(nums[i]>k){
                    res+=abs(1LL*nums[i]-k);
                }
            }
        }else{
            for(int i=idx;i<n;i++){
                if(nums[i]<k){
                    res+=abs(1LL*nums[i]-k);
                }
            }
        }
        return res;
    }

4.带权图里旅途的最小代价

可以发现题意是找连通图内权值按位与的最小路径值，由于是与操作，权值越&越小，转而求连通块内的所有路径权值的与

step1：将edges转化成邻接表

step2：bfs求出每个点所属的连通块km和每个连通块内全部路径的与值ans

step3：求询问，若x=y，答案为0，若km[x]==km[y]，答案为ans[km[x]]，反之答案为-1

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        vector<vector<pair<int,int>>> g(n);
        for(auto edge:edges){
            int x=edge[0],y=edge[1],z=edge[2];
            g[x].emplace_back(y,z);
            g[y].emplace_back(x,z);
        }
        int cnt=1;
        vector<int> km(n),ans(n+1,INT_MAX);
        // function<void(int)> dfs=[&](int i){
        //     km[i]=cnt;
        //     for(auto &[j,w]:g[i]){
        //         ans[cnt]&=w;
        //         if(!km[j]) {
        //             km[j]=cnt;
        //             dfs(j);
        //         }
        //     }
        // };
        auto bfs = [&](int i) {
            queue<int> q;
            q.push(i); km[i]=cnt;
            while (!q.empty()) {
                int i=q.front();q.pop();
                for (auto &[j,w]:g[i]) {
                    ans[cnt]&=w;
                    if (!km[j]) q.push(j), km[j] = cnt;
                }
            }
        };

        for(int i=0;i<n;i++)
            if(!km[i])
                bfs(i),cnt++;
        
        vector<int> res;
        for(auto q:query){
            int x=q[0],y=q[1];
            if(x==y) res.push_back(0);
            else if(km[x]==km[y])   res.push_back(ans[km[x]]);
            else res.push_back(-1);
        }
        return res;
    }