**描述**：给定一个二进制数组 $nums$，可以最多将 $1$ 个 $0$ 翻转为 $1$。

**要求**：如果最多可以翻转一个 $0$，则返回数组中连续 $1$ 的最大个数。

**说明**：

- 1 <= nums.length <= 105

nums[i] 不是 0 就是 1.

**示例**：

- 示例 1：

输入：nums = [1,0,1,1,0]

输出：4

解释：翻转第一个 0 可以得到最长的连续 1。当翻转以后，最大连续 1 的个数为 4。

- 示例 2：

输入：nums = [1,0,1,1,0,1]

输出：4

我们可以使用滑动窗口来解决问题。保证滑动窗口内最多有 $1$ 个 $0$。具体做法如下：

设定两个指针：$left$、$right$，分别指向滑动窗口的左右边界，保证滑动窗口内最多有 $1$ 个 $0$。使用 $zero\underline{}count$ 统计窗口内 $1$ 的个数。使用 $ans$ 记录答案。

- 一开始，$left$、$right$ 都指向 $0$。

- 如果 $nums[right] == 0$，则窗口内 $1$ 的个数加 $1$。

- 如果该窗口中 $1$ 的个数多于 $1$ 个，即 $zero\underline{}count > 1$，则不断右移 $left$，缩小滑动窗口长度，并更新窗口中 $1$ 的个数，直到 $zero\underline{}count \le 1$。

- 维护更新最大连续 $1$ 的个数。然后右移 $right$，直到 $right \ge len(nums)$ 结束。

- 输出最大连续 $1$ 的个数。

- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $nums$ 的长度。

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

- 标签：栈、字符串

- 难度：简单

- [1021. 删除最外层的括号 - 力扣](https://leetcode.cn/problems/remove-outermost-parentheses/)

**描述**：有效括号字符串为空 `""`、`"("` + $A$ + `")"` 或 $A + B$ ，其中 $A$ 和 $B$ 都是有效的括号字符串，$+$ 代表字符串的连接。

- 例如，`""`，`"()"`，`"(())()"` 和 `"(()(()))"` 都是有效的括号字符串。

如果有效字符串 $s$ 非空，且不存在将其拆分为 $s = A + B$ 的方法，我们称其为原语（primitive），其中 $A$ 和 $B$ 都是非空有效括号字符串。

给定一个非空有效字符串 $s$，考虑将其进行原语化分解，使得：$s = P_1 + P_2 + ... + P_k$，其中 $P_i$ 是有效括号字符串原语。

**要求**：对 $s$ 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 $s$。

**说明**：

- $1 \le s.length \le 10^5$。

- $s[i]$ 为 `'('` 或 `')'`。

- $s$ 是一个有效括号字符串。

**示例**：

- 示例 1：

输入：s = "(()())(())"

输出："()()()"

解释：

输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，

删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

- 示例 2：

输入：s = "(()())(())(()(()))"

输出："()()()()(())"

解释：

输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，

删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

题目要求我们对 $s$ 进行原语化分解，并且删除分解中每个原语字符串的最外层括号。

通过观察可以发现，每个原语其实就是一组有效的括号对（左右括号匹配时），此时我们需要删除这组有效括号对的最外层括号。

我们可以使用一个计数器 $cnt$ 来进行原语化分解，并删除每个原语的最外层括号。

当计数器遇到左括号时，令计数器 $cnt$ 加 $1$，当计数器遇到右括号时，令计数器 $cnt$ 减 $1$。这样当计数器为 $0$ 时表示当前左右括号匹配。

为了删除每个原语的最外层括号，当遇到每个原语最外侧的左括号时（此时 $cnt$ 必然等于 $0$，因为之前字符串为空或者为上一个原语字符串），因为我们不需要最外层的左括号，所以此时我们不需要将其存入答案字符串中。只有当 $cnt > 0$ 时，才将其存入答案字符串中。

同理，当遇到每个原语最外侧的右括号时（此时 $cnt$ 必然等于 $1$，因为之前字符串差一个右括号匹配），因为我们不需要最外层的右括号，所以此时我们不需要将其存入答案字符串中。只有当 $cnt > 1$ 时，才将其存入答案字符串中。

具体步骤如下：

1. 遍历字符串 $s$。

2. 如果遇到 `'('`，判断当前计数器是否大于 $0$：

1. 如果 $cnt > 0$，则将 `'('` 存入答案字符串中，并令计数器加 $1$，即：`cnt += 1`。

2. 如果 $cnt == 0$，则令计数器加 $1$，即：`cnt += 1`。

3. 如果遇到 `')'`，判断当前计数器是否大于 $1$：

1. 如果 $cnt > 1$，则将 `')'` 存入答案字符串中，并令计数器减 $1$，即：`cnt -= 1`。

2. 如果 $cnt == 1$，则令计数器减 $1$，即：`cnt -= 1`。

4. 遍历完返回答案字符串 $ans$。

class Solution:

def removeOuterParentheses(self, s: str) -> str:

cnt, ans = 0, ""

for ch in s:

if ch == '(':

if cnt > 0:

ans += ch

cnt += 1

else:

if cnt > 1:

ans += ch

cnt -= 1

return ans

- **时间复杂度**：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。

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

- 标签：贪心、数组

- 难度：简单

- [1827. 最少操作使数组递增 - 力扣](https://leetcode.cn/problems/minimum-operations-to-make-the-array-increasing/)

**描述**：给定一个整数数组 $nums$（下标从 $0$ 开始）。每一次操作中，你可以选择数组中的一个元素，并将它增加 $1$。

- 比方说，如果 $nums = [1,2,3]$，你可以选择增加 $nums[1]$ 得到 $nums = [1,3,3]$。

**要求**：请你返回使 $nums$ 严格递增的最少操作次数。

**说明**：

- 我们称数组 $nums$ 是严格递增的，当它满足对于所有的 $0 \le i < nums.length - 1$ 都有 $nums[i] < nums[i + 1]$。一个长度为 $1$ 的数组是严格递增的一种特殊情况。

- $1 \le nums.length \le 5000$。

- $1 \le nums[i] \le 10^4$。

**示例**：

- 示例 1：

输入：nums = [1,1,1]

输出：3

解释：你可以进行如下操作：

1) 增加 nums[2] ，数组变为 [1,1,2]。

2) 增加 nums[1] ，数组变为 [1,2,2]。

3) 增加 nums[2] ，数组变为 [1,2,3]。

- 示例 2：

输入：nums = [1,5,2,4,1]

输出：14

题目要求使 $nums$ 严格递增的最少操作次数。当遇到 $nums[i - 1] \ge nums[i]$ 时，我们应该在满足要求的同时，尽可能使得操作次数最少，则 $nums[i]$ 应增加到 $nums[i - 1] + 1$ 时，此时操作次数最少，并且满足 $nums[i - 1] < nums[i]$。

具体操作步骤如下：

1. 从左到右依次遍历数组元素。

2. 如果遇到 $nums[i - 1] \ge nums[i]$ 时：

1. 本次增加的最少操作次数为 $nums[i - 1] + 1 - nums[i]$，将其计入答案中。

2. 将 $nums[i]$ 变为 $nums[i - 1] + 1$。

3. 遍历完返回答案 $ans$。

class Solution:

def minOperations(self, nums: List[int]) -> int:

ans = 0

for i in range(1, len(nums)):

if nums[i - 1] >= nums[i]:

ans += nums[i - 1] + 1 - nums[i]

nums[i] = nums[i - 1] + 1

return ans

- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $nums$ 的长度。

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