feat: add solutions for lc No.3891 by yanglbme · Pull Request #5137 · doocs/leetcode

yanglbme · 2026-04-06T12:35:30Z

No description provided.

Copilot

Pull request overview

Adds multi-language solution implementations and documentation for LeetCode 3891 (“Minimum Increase to Maximize Special Indices”) in the solution/3800-3899/3891... directory.

Changes:

Added solution implementations in TypeScript, Python, Java, Go, and C++.
Expanded the algorithm explanation and embedded code snippets in README.md / README_EN.md.

Reviewed changes

Copilot reviewed 7 out of 7 changed files in this pull request and generated 6 comments.

Show a summary per file

File	Description
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/Solution.ts	Adds a memoized DFS implementation in TypeScript.
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/Solution.py	Adds a memoized DFS implementation in Python using `@cache`.
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/Solution.java	Adds a memoized DFS implementation in Java with `Long[][]` memo.
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/Solution.go	Adds a memoized DFS implementation in Go using `int64` memo.
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/Solution.cpp	Adds a memoized DFS implementation in C++ using `long long` memo.
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/README.md	Adds a Chinese explanation and code snippets for multiple languages.
solution/3800-3899/3891.Minimum Increase to Maximize Special Indices/README_EN.md	Updates solution section, but currently contains Chinese text.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

Copilot · 2026-04-06T12:39:37Z

+        @cache
+        def dfs(i: int, j: int) -> int:
+            if i >= len(nums) - 1:
+                return 0
+            cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])
+            ans = cost + dfs(i + 2, j)
+            if j:
+                ans = min(ans, dfs(i + 1, 0))
+            return ans
+
+        return dfs(1, len(nums) & 1 ^ 1)


The memoized DFS is recursive and for n up to 1e5 (see constraints) it can reach ~n/2 call depth, which will hit Python's recursion limit and crash. Consider rewriting this as iterative DP (bottom-up over i with 2 states for j) instead of recursion.

Suggested change

@cache

def dfs(i: int, j: int) -> int:

if i >= len(nums) - 1:

return 0

cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])

ans = cost + dfs(i + 2, j)

if j:

ans = min(ans, dfs(i + 1, 0))

return ans

return dfs(1, len(nums) & 1 ^ 1)

n = len(nums)

dp0 = [0] * (n + 2)

dp1 = [0] * (n + 2)

for i in range(n - 2, 0, -1):

cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])

dp0[i] = cost + dp0[i + 2]

dp1[i] = min(cost + dp1[i + 2], dp0[i + 1])

return dp1[1] if (len(nums) & 1 ^ 1) else dp0[1]

Copilot · 2026-04-06T12:39:38Z

+                ans = min(ans, dfs(i + 1, 0))
+            return ans
+
+        return dfs(1, len(nums) & 1 ^ 1)


This uses @cache but returns dfs(...) directly without clearing the cache. In this repo, cached dfs helpers are typically followed by dfs.cache_clear() before returning to avoid cached state persisting across test runs; assign the result to a variable, clear the cache, then return it.

Suggested change

return dfs(1, len(nums) & 1 ^ 1)

result = dfs(1, len(nums) & 1 ^ 1)

dfs.cache_clear()

return result

Copilot · 2026-04-06T12:39:38Z

+    private Long[][] f;
+    private int[] nums;
+    private int n;
+
+    public long minIncrease(int[] nums) {
+        n = nums.length;
+        this.nums = nums;
+        f = new Long[n][2];
+        return dfs(1, n & 1 ^ 1);
+    }
+
+    private long dfs(int i, int j) {
+        if (i >= n - 1) {
+            return 0;
+        }
+        if (f[i][j] != null) {
+            return f[i][j];
+        }
+        int cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);
+        long ans = cost + dfs(i + 2, j);
+        if (j > 0) {
+            ans = Math.min(ans, dfs(i + 1, 0));
+        }
+        return f[i][j] = ans;


The recursive dfs can reach ~n/2 depth when n=1e5, which is very likely to trigger StackOverflowError in Java. Consider converting to an iterative bottom-up DP with two states (j=0/1) to avoid deep recursion.

Suggested change

private Long[][] f;

private int[] nums;

private int n;

public long minIncrease(int[] nums) {

n = nums.length;

this.nums = nums;

f = new Long[n][2];

return dfs(1, n & 1 ^ 1);

}

private long dfs(int i, int j) {

if (i >= n - 1) {

return 0;

}

if (f[i][j] != null) {

return f[i][j];

}

int cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);

long ans = cost + dfs(i + 2, j);

if (j > 0) {

ans = Math.min(ans, dfs(i + 1, 0));

}

return f[i][j] = ans;

public long minIncrease(int[] nums) {

int n = nums.length;

long[][] dp = new long[n + 2][2];

for (int i = n - 2; i >= 1; --i) {

int cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);

dp[i][0] = cost + dp[i + 2][0];

dp[i][1] = Math.min(cost + dp[i + 2][1], dp[i + 1][0]);

}

return dp[1][(n & 1) ^ 1];

Copilot · 2026-04-06T12:39:38Z

+    const f: number[][] = Array.from({ length: n }, () => Array(2).fill(-1));
+
+    const dfs = (i: number, j: number): number => {
+        if (i >= n - 1) {
+            return 0;
+        }
+        if (f[i][j] !== -1) {
+            return f[i][j];
+        }
+
+        const cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);
+        let ans = cost + dfs(i + 2, j);
+
+        if (j > 0) {
+            ans = Math.min(ans, dfs(i + 1, 0));
+        }
+
+        f[i][j] = ans;
+        return ans;
+    };
+
+    return dfs(1, (n & 1) ^ 1);


This solution relies on deep recursion; with n up to 1e5 the recursion depth can be ~5e4, which will overflow the JS/TS call stack in typical runtimes. Consider rewriting dfs as an iterative DP (compute answers for i from n-2 down to 1 with j in {0,1}) to avoid stack overflow.

Suggested change

const f: number[][] = Array.from({ length: n }, () => Array(2).fill(-1));

const dfs = (i: number, j: number): number => {

if (i >= n - 1) {

return 0;

}

if (f[i][j] !== -1) {

return f[i][j];

}

const cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);

let ans = cost + dfs(i + 2, j);

if (j > 0) {

ans = Math.min(ans, dfs(i + 1, 0));

}

f[i][j] = ans;

return ans;

};

return dfs(1, (n & 1) ^ 1);

const f: number[][] = Array.from({ length: n + 2 }, () => Array(2).fill(0));

for (let i = n - 2; i >= 1; --i) {

const cost = Math.max(0, Math.max(nums[i - 1], nums[i + 1]) + 1 - nums[i]);

for (let j = 0; j < 2; ++j) {

let ans = cost + f[i + 2][j];

if (j > 0) {

ans = Math.min(ans, f[i + 1][0]);

}

f[i][j] = ans;

}

}

return f[1][(n & 1) ^ 1];

Copilot · 2026-04-06T12:39:38Z

+### 方法一：记忆化搜索
+
+我们注意到，如果数组长度为奇数，那么将所有奇数下标的元素增加到比相邻元素都大 1 就可以得到最大数量的特殊下标；如果数组长度为偶数，那么将下标范围为 $[1, n - 2]$ 中的下标，跳过其中一个，剩余的元素，按隔一个元素选择一个的方式增加到比相邻元素都大 1 就可以得到最大数量的特殊下标。
+
+因此，我们设计一个函数 $\text{dfs}(i, j)$，表示从下标 $i$ 开始，跳过 $j$ 个元素，得到的最大数量的特殊下标所需的最少操作数。对于每个下标 $i$，我们可以选择将其增加到比相邻元素都大 1，或者跳过它。我们使用记忆化搜索来避免重复计算。
+
+函数 $\text{dfs}(i, j)$ 的实现如下：
+
+- 如果 $i \geq n - 1$，返回 0。
+- 计算将 $nums[i]$ 增加到比相邻元素都大 1 所需的操作数，记为 $cost$。
+- 计算选择将 $nums[i]$ 增加到比相邻元素都大 1 的总操作数 $cost + \text{dfs}(i + 2, j)$。
+- 如果 $j > 0$，计算选择跳过 $nums[i]$ 的总操作数 $\text{dfs}(i + 1, 0)$，并更新 $ans$ 为两者的较小值。
+
+最后，返回 $\text{dfs}(1, (n \& 1) \oplus 1)$ 即可。
+
+时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。


README_EN.md is intended to be an English explanation, but the entire solution section (title and prose) is in Chinese (e.g., "方法一：记忆化搜索"). Please translate this section to English (and keep the Chinese version in README.md).

Suggested change

### 方法一：记忆化搜索

我们注意到，如果数组长度为奇数，那么将所有奇数下标的元素增加到比相邻元素都大 1 就可以得到最大数量的特殊下标；如果数组长度为偶数，那么将下标范围为 $[1, n - 2]$ 中的下标，跳过其中一个，剩余的元素，按隔一个元素选择一个的方式增加到比相邻元素都大 1 就可以得到最大数量的特殊下标。

因此，我们设计一个函数 $\text{dfs}(i, j)$，表示从下标 $i$ 开始，跳过 $j$ 个元素，得到的最大数量的特殊下标所需的最少操作数。对于每个下标 $i$，我们可以选择将其增加到比相邻元素都大 1，或者跳过它。我们使用记忆化搜索来避免重复计算。

函数 $\text{dfs}(i, j)$ 的实现如下：

- 如果 $i \geq n - 1$，返回 0。

- 计算将 $nums[i]$ 增加到比相邻元素都大 1 所需的操作数，记为 $cost$。

- 计算选择将 $nums[i]$ 增加到比相邻元素都大 1 的总操作数 $cost + \text{dfs}(i + 2, j)$。

- 如果 $j > 0$，计算选择跳过 $nums[i]$ 的总操作数 $\text{dfs}(i + 1, 0)$，并更新 $ans$ 为两者的较小值。

最后，返回 $\text{dfs}(1, (n \& 1) \oplus 1)$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。

### Solution 1: Memoized Search

We observe that if the length of the array is odd, then increasing all elements at odd indices so that each becomes 1 greater than both adjacent elements will produce the maximum number of special indices. If the length of the array is even, then among the indices in the range $[1, n - 2]$, we skip exactly one index, and for the remaining indices, choose every other one to increase so that each becomes 1 greater than both adjacent elements. This also yields the maximum number of special indices.

Therefore, we design a function $\text{dfs}(i, j)$, which represents the minimum number of operations needed to obtain the maximum number of special indices starting from index $i$, while skipping $j$ elements. For each index $i$, we can either increase it so that it is 1 greater than both adjacent elements, or skip it. We use memoized search to avoid repeated computations.

The implementation of $\text{dfs}(i, j)$ is as follows:

- If $i \geq n - 1$, return 0.

- Compute the number of operations required to increase $nums[i]$ so that it is 1 greater than both adjacent elements, denoted as $cost$.

- Compute the total cost of choosing to increase $nums[i]$: $cost + \text{dfs}(i + 2, j)$.

- If $j > 0$, compute the total cost of choosing to skip $nums[i]$: $\text{dfs}(i + 1, 0)$, and update $ans$ to the smaller of the two.

Finally, return $\text{dfs}(1, (n \& 1) \oplus 1)$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array.

Copilot · 2026-04-06T12:39:39Z

+        @cache
+        def dfs(i: int, j: int) -> int:
+            if i >= len(nums) - 1:
+                return 0
+            cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])
+            ans = cost + dfs(i + 2, j)
+            if j:
+                ans = min(ans, dfs(i + 1, 0))
+            return ans
+
+        return dfs(1, len(nums) & 1 ^ 1)


The Python snippet uses deep recursion (dfs) with potential depth ~n/2 for n up to 1e5, which will exceed Python's recursion limit in practice. If the implementation is changed to iterative DP (recommended), please update this snippet accordingly (and include cache_clear if @cache is kept).

Suggested change

@cache

def dfs(i: int, j: int) -> int:

if i >= len(nums) - 1:

return 0

cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])

ans = cost + dfs(i + 2, j)

if j:

ans = min(ans, dfs(i + 1, 0))

return ans

return dfs(1, len(nums) & 1 ^ 1)

n = len(nums)

dp0 = [0] * (n + 2)

dp1 = [0] * (n + 2)

for i in range(n - 2, 0, -1):

cost = max(0, max(nums[i - 1], nums[i + 1]) + 1 - nums[i])

dp0[i] = cost + dp0[i + 2]

dp1[i] = min(cost + dp1[i + 2], dp0[i + 1])

return dp1[1] if ((n & 1) ^ 1) else dp0[1]

feat: add solutions for lc No.3891

cad8bc2

Copilot AI review requested due to automatic review settings April 6, 2026 12:35

Copilot started reviewing on behalf of yanglbme April 6, 2026 12:36 View session

Update README.md

25e5dfe

Copilot AI reviewed Apr 6, 2026

View reviewed changes

Update README with English solution explanation

f2ee006

yanglbme merged commit 023ed13 into main Apr 6, 2026
6 checks passed

yanglbme deleted the dev branch April 6, 2026 12:40

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

feat: add solutions for lc No.3891#5137

feat: add solutions for lc No.3891#5137
yanglbme merged 3 commits intomainfrom
dev

yanglbme commented Apr 6, 2026

Uh oh!

Copilot AI left a comment

Uh oh!

Copilot AI Apr 6, 2026

Uh oh!

Copilot AI Apr 6, 2026

Uh oh!

Copilot AI Apr 6, 2026

Uh oh!

Copilot AI Apr 6, 2026

Uh oh!

Copilot AI Apr 6, 2026

Uh oh!

Copilot AI Apr 6, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

-        return dfs(1, len(nums) & 1 ^ 1)
+        result = dfs(1, len(nums) & 1 ^ 1)
+        dfs.cache_clear()
+        return result

Uh oh!

Conversation

yanglbme commented Apr 6, 2026

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Copilot AI Apr 6, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Apr 6, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Apr 6, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Apr 6, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Apr 6, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Apr 6, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants