力扣周赛：力扣第407场周赛

力扣第407场周赛：将 1 移动到末尾的最大操作次数、使数组等于目标数组所需的最少操作次数，涉及思维、单调栈、分类讨论等知识点。

T3-将 1 移动到末尾的最大操作次数

题目描述

给你一个 二进制字符串 $s$。

你可以对这个字符串执行任意次下述操作：

• 选择字符串中的任一下标 $i$（ $i+1<s.length$ ），该下标满足 $s[i]==1且s[i+1]==0$。
• 将字符 $s[i]$ 向右移直到它到达字符串的末端或另一个 $1$。

例如，对于 $s$ = “010010”，如果我们选择 $i=1$，结果字符串将会是 $s$ = “000110”。

返回你能执行的最大操作次数。

数据范围

• $1<=s.length<=10^5$
• $s[i]$ 为 $0$ 或 $1$。

解题思路

考虑如下移动方案

1. 移动第 $1$ 个 $1$，操作次数合计为 $1$；
2. 移动第 $2$ 个 $1$，然后又可以移动第 $1$ 个 $1$，操作次数合计为 $2$；
3. 移动第 $3$ 个 $1$，然后又可以移动第 $2$ 个 $1$，然后又可以移动第 $1$ 个 $1$，操作次数合计为 $3$；
4. 以此类推。

注意，并非每个 $1$ 都可以移动。

代码实现

int maxOperations(string s) {
    int n = s.size(), res = 0, r = n - 1, c1 = 0;
    for (int i = 0; i < r; i++) {
        if (s[i] == '1') {
            // 记录当前1的个数
            c1++;
            // 1的后面如果是0，则现在可以移动
            if (s[i + 1] == '0')res += c1;
        }
    }
    return res;
}

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

T4-使数组等于目标数组所需的最少操作次数

题目描述

给你两个长度相同的正整数数组 $nums$ 和 $target$。

在一次操作中，你可以选择 $nums$ 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。

返回使 $nums$ 数组变为 $target$ 数组所需的最少操作次数。

数据范围

• $1<=nums.length==target.length<=10^5$
• $1<=nums[i],target[i]<=10^8$

解题思路

令 $v[i]=num[i]-target[i]$，要使得 $nums$ 变为 $target$，等价于使得 $v[i]$ 全为 $0$。

$v[i]$ 由若干如下数段组成：连续正数段、连续负数段、连续 $0$ 段。

注意，数段需满足与数段相邻的数的符号与数段不同，$0$ 既不是正数也不是负数。举个例子，若连续正数段 $a$ 和 $b$ 相邻，则 $a$ 和 $b$ 应视为一个连续正数段。

对于每个数段，单独处理。既然数段之间互不影响，则可将连续负数段转为连续正数段处理，又由于连续 $0$ 段已满足题目要求，故不处理。所以，只需要处理连续正数段即可。

连续且相等的若干个数可视作同一个数，视作同一个数不影响操作次数。

准备单调栈 $sk$，对于一个连续正数段 $a$，考虑将 $a_i$ 入栈：

1. 若栈为空或者 $a_i>sk.top$ ，则直接入栈。
2. 否则，若 $a_i=sk.top$，可视作同一个数，$a_i$ 不入栈，忽略。
3. 否则，令 $x=sk.top$，栈顶元素出栈
   • 若栈为空，则操作 $x-a_i$ 次，使得 $x$ 变成 $a_i$，$a_i$ 入栈。$x$ 和 $a_i$ 现在被视作同一个数，仅让 $a_i$ 留在栈中即可，后续不用考虑 $x$。
   • 若栈不为空，则比较 $sk.top$ 和 $a_i$
     • 若 $sk.top＞a_i$，则操作 $x-sk.top$ 次，将 $x$ 变成 $sk.top$， 回到步骤 $1$。
     • 否则，操作 $x-a_i$ 次，将 $x$ 变成 $a_i$，若$a_i!=sk.top$ 则入栈，否则忽略。

代码实现

long long minimumOperations(vector<int> &nums, vector<int> &target) {
    typedef long long ll;
    int n = nums.size();
    auto &v = nums;
    for (int i = 0; i < n; i++)v[i] -= target[i];
    // 逐一处理每段
    int l = 0, r, sk[n], tp;
    ll res = 0;
    while (l < n) {
        // 重置栈指针
        tp = -1;
        // 找非零段
        while (l < n && !v[l])l++;
        if ((r = l) >= n)break;
        // 处理非零段
        for (int tv; r < n && v[r] && (v[l] ^ v[r]) >= 0; r++) {
            tv = abs(v[r]);
            while (tp != -1 && sk[tp] > tv) {
                int x = sk[tp--];
                if (tp == -1 || sk[tp] < tv)res += x - tv;
                else res += x - sk[tp];
            }
            // 待入栈元素与栈顶元素相同时无需入栈
            if (tp == -1 || sk[tp] != v[r]) sk[++tp] = tv;
        }
        // 处理栈中剩余元素
        while (tp != -1) {
            int x = sk[tp--];
            res += tp == -1 ? x : x - sk[tp];
        }
        // 换下一个区间
        l = r;
    }
    return res;
}

时间复杂度：$O(n)$，每个元素最多入栈 $1$ 次、出栈 $1$ 次。

空间复杂度：$O(n)$。

END

文章文档：公众号 字节幺零二四 回复关键字可获取本文文档。

题目来源：力扣第407场双周赛

文章声明：题目来源 力扣 平台，如有侵权，请联系删除！

原文地址：https://blog.csdn.net/qq_53469830/article/details/140592490

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！