刷题记录帖子

LC. 1306. Jump Game III

题目本质

把 数组当成图

每个 index 是一个节点

从 index i 可以跳到：

i + arr[i]

i - arr[i]

问：从 start 出发，能否到达任意值为 0 的节点

➡️ 典型的图可达性问题

二、为什么不能用 Greedy / DP？

不是单方向

可以左右来回跳

有环（会无限循环）

✅ 必须防止重复访问

➡️ 直接上 BFS / DFS

三、标准解法：BFS（或 DFS）
BFS 更直观的原因

不关心最短路径，只关心「能不能到」

状态空间 ≤ n

每个 index 最多访问一次

1. from collections import deque
   
2. 
   
3. class Solution:
   
4.     def canReach(self, arr: List[int], start: int) -> bool:
   
5.         n = len(arr)
   
6.         visited = [False] * n
   
7.         queue = deque([start])
   
8.         visited[start] = True   # ⭐ 提前标记
   
9. 
   
10.         while queue:
    
11.             curr = queue.popleft()
    
12. 
    
13.             if arr[curr] == 0:
    
14.                 return True
    
15. 
    
16.             for ind in (curr - arr[curr], curr + arr[curr]):
    
17.                 if 0 <= ind < n and not visited[ind]:
    
18.                     visited[ind] = True   # ⭐ 入队即标记
    
19.                     queue.append(ind)
    
20. 
    
21.         return False
    

复制代码

LC 1345. Jump Game IV

虽然是 Hard 但是如果从 Jump Game I 一路做上来，会发现这就是多加了一个 connection same values 的起点，还是 BFS 找最短的层遍历的套路。

这道题用 BFS 层序遍历求最少跳数：

建图：用哈希表记录相同值的所有索引位置
BFS：从索引 0 开始，每次可以跳到 i-1、i+1 或任何 arr[i] 值相同的位置
剪枝优化：访问过相同值的连接后立即删除，避免重复遍历
层序计数：每遍历完一层，跳数 +1，第一次到达 n-1 就是最短路径

核心：BFS 保证最短路径 + 删除已用连接避免超时。

1. class Solution:
   
2.     def minJumps(self, arr: List[int]) -> int:
   
3.         n = len(arr)
   
4.         same_values_connections = defaultdict(list)
   
5.         for i in range(n):
   
6.             same_values_connections[arr[i]].append(i)
   
7.         
   
8.         visited = [False] * n
   
9.         queue = deque([0])
   
10.         visited[0] = True
    
11.         jumps = 0
    
12.         
    
13.         while queue:
    
14.             current_level_length = len(queue)  # 每层开始时计算
    
15.             
    
16.             for _ in range(current_level_length):  # 处理当前层的所有节点
    
17.                 curr = queue.popleft()
    
18.                
    
19.                 # 到达终点
    
20.                 if curr == n - 1:
    
21.                     return jumps
    
22.                
    
23.                 # 向左右跳
    
24.                 for nx_jump in (curr - 1, curr + 1):
    
25.                     if 0 <= nx_jump < n and not visited[nx_jump]:
    
26.                         visited[nx_jump] = True  # 立即标记
    
27.                         queue.append(nx_jump)
    
28.                
    
29.                 # 跳到相同值的位置
    
30.                 if arr[curr] in same_values_connections:
    
31.                     for ind in same_values_connections[arr[curr]]:
    
32.                         if not visited[ind]:
    
33.                             visited[ind] = True  # 立即标记
    
34.                             queue.append(ind)
    
35.                     # 立刻 remove
    
36.                     del same_values_connections[arr[curr]]
    
37.             
    
38.             jumps += 1  # 完成一层后，跳数加1
    
39.         
    
40.         return -1  # 理论上不会到这里

复制代码

LC 1340. Jump Game V

Return the maximum number of indices you can visit.

DFS + 记忆化搜索（动态规划） 问题

首先，每个位置都要测试下，看这个位置能跳多少步， 因为新加入的一个数，会改变整体的地形地貌，最终改变结果。

我们需要 DFS，测算当前 index 能覆盖多少坐标。

为了减少计算压力，我们用 memo 来记忆，每个 index 如果已经跑过 DFS 那么它的最多覆盖 index 是多少。

解题步骤

DFS 搜索：从位置 i 开始，尝试向左右跳（距离 1 到 d）
跳跃条件：arr[i] > arr[j] 且中间没有 >= arr[i] 的障碍
记忆化：memo[i] 存储从 i 出发能访问的最大节点数
答案：遍历所有起点，取最大值

1. class Solution:
   
2.     def maxJumps(self, arr: List[int], d: int) -> int:
   
3.         memos = defaultdict(int) # store maximum number of index you can visit
   
4. 
   
5.         def DFS(ind):
   
6.             if ind in memos:
   
7.                 # have visited the index
   
8.                 return memos[ind]
   
9. 
   
10.             max_visits = 1  # 至少访问当前位置
    
11. 
    
12.             # go to left
    
13.             for i in range(ind - 1, max(ind - d - 1, -1), -1):
    
14.                 if arr[i] >= arr[ind]: break # 高墙阻挡
    
15.                 max_visits = max(max_visits, 1 + DFS(i))
    
16. 
    
17.             # go to right
    
18.             for i in range(ind + 1, min(ind + d + 1, len(arr)), 1):
    
19.                 if arr[i] >= arr[ind]: break # 右侧高墙阻挡
    
20.                 max_visits = max(max_visits, 1 + DFS(i))
    
21. 
    
22.             memos[ind] = max_visits
    
23. 
    
24.             return max_visits
    
25.         res = []
    
26. 
    
27.         for ind in range(len(arr)):
    
28.             res.append(DFS(ind))
    
29.         
    
30.         return max(res)

复制代码

1696. Jump Game VI

1. class Solution:
   
2.     def maxResult(self, nums: List[int], k: int) -> int:
   
3.         # dp[i] is the largest sum of path to i
   
4.         # n = len(nums)
   
5.         # dp = [float('-inf')] * n
   
6.         # if n == 1: return nums[0]
   
7.         # dp[0] = nums[0]
   
8.         # dp[1] = (nums[0]+nums[1])
   
9. 
   
10.         # # dp[i] = max(dp[max(0, i-k)], ......, dp[i-1])
    
11. 
    
12.         # for i in range(n):
    
13.         #     # Check index before i to see if it contributes larger j
    
14. 
    
15.         #     for j in range(max(0, i-k), i):
    
16.         #         print(dp, j, i)
    
17.         #         dp[i] = max(dp[j] + nums[i], dp[i])
    
18.         
    
19.         # return dp[-1]
    
20. 
    
21.          # dp[i] = max(dp[max(0, i-k)], ......, dp[i-1])
    
22. 
    
23.         # dp[i] is the largest sum of path to i
    
24.         n = len(nums)
    
25.         if n == 1: return nums[0]
    
26.         dp = [float('-inf')] * n
    
27.         dp[0] = nums[0]
    
28.         
    
29. 
    
30.         dq = deque([0])
    
31. 
    
32.         for i in range(1, n):
    
33.             # remove out of index in dq
    
34.             while dq and i - dq[0] > k:
    
35.                 dq.popleft()
    
36. 
    
37.             # update dp
    
38.             dp[i] = nums[i] + dp[dq[0]]
    
39. 
    
40.             # update Monotonic queue
    
41.             while dq and dp[dq[-1]] < dp[i]:
    
42.                 dq.pop()
    
43. 
    
44.             dq.append(i)
    
45. 
    
46.         return dp[-1]
    
47. 
    
48. 
    
49.       
    
50.         

复制代码

Jump Game VI 题目总结
题目类型
动态规划 + 单调队列优化（滑动窗口最大值）

核心思路
1. DP 定义
dp[i] = 到达索引 i 时能获得的最大分数
2. 状态转移方程
dp[i] = nums[i] + max(dp[i-k], dp[i-k+1], ..., dp[i-1])
                   └─────────────────────────────┘
                        前 k 个位置的最大值
3. 为什么需要优化？

朴素 DP：O(n × k) → 每次遍历 k 个位置找最大值 → TLE
单调队列：O(n) → 用队列维护滑动窗口最大值 → AC


单调队列优化原理
核心思想
维护一个单调递减的双端队列，队首始终是窗口内 dp 值最大的索引。
队列维护规则
操作条件目的移除队首i - dq[0] > k索引超出窗口范围 [i-k, i-1]移除队尾dp[dq[-1]] <= dp[i]新值更大，旧值永远不会是最大值加入队尾每次循环当前索引可能是未来的最大值

LC1871. Jump Game VII

1. from collections import deque
   
2. 
   
3. class Solution:
   
4.     def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
   
5.         # 如果终点是 '1'，一定不可能站上去，直接返回
   
6.         if s[-1] == '1':
   
7.             return False
   
8. 
   
9.         n = len(s)
   
10. 
    
11.         # visited[i] 表示：位置 i 是否已经确认「可以站到」
    
12.         visited = [False] * n
    
13.         visited[0] = True
    
14. 
    
15.         # BFS 队列：存放所有「已经可以站到」的位置
    
16.         queue = deque([0])
    
17. 
    
18.         # farthest 表示：目前为止，已经“扫描检查过”的最右下标
    
19.         # 小于等于 farthest 的位置，后面都不需要再看
    
20.         farthest = 0
    
21. 
    
22.         while queue:
    
23.             i = queue.popleft()
    
24. 
    
25.             # 从位置 i 出发，理论上能跳到：
    
26.             # [i + minJump, i + maxJump]
    
27.             #
    
28.             # 但为了避免重复扫描，只检查：
    
29.             # 从 farthest + 1 开始的“新区域”
    
30.             start = max(i + minJump, farthest + 1)
    
31.             end = min(i + maxJump, n - 1)
    
32. 
    
33.             # 扫描这一段区间
    
34.             for j in range(start, end + 1):
    
35.                 # 只有 '0' 才能站，而且必须是第一次访问
    
36.                 if s[j] == '0' and not visited[j]:
    
37.                     visited[j] = True
    
38.                     queue.append(j)
    
39. 
    
40.             # 更新已经扫描到的最右边界
    
41.             # 之后所有 <= end 的位置都不会再被重复检查
    
42.             farthest = end
    
43. 
    
44.         # 看最终位置是否被标记为可达
    
45.         return visited[-1]
    

复制代码

1️⃣ 这道题本质是什么？

在一维数组上做 BFS，但跳跃范围是一个区间

每个能站的位置 i

可以跳到区间
[i + minJump, i + maxJump]

只能落在 '0' 上

问：能不能到最后一个位置

👉 本质是 区间可达性 + BFS

2️⃣ 为什么不能「暴力 BFS」？

如果直接做 BFS：

每个 i 都扫一遍 [i+minJump, i+maxJump]

最坏情况：
n * (maxJump - minJump)
→ O(n²)，必 TLE

👉 必须 避免重复扫描区间

3️⃣ 核心优化思想（本题灵魂）
🔑 关键变量：farthest
farthest = 已经扫描过的最右边界


含义是：

所有 ≤ farthest 的位置，都已经被“检查过能不能站”

所以：

之后再遇到新的 i

只需要扫描：

max(i + minJump, farthest + 1)
到
min(i + maxJump, n - 1)


📌 每个 index 只会被扫描一次

4️⃣ BFS 的真正含义（非常容易误解）
❌ 错误理解

queue 里是「下一步要跳到的位置」

✅ 正确理解

queue 里是「已经确认可以站到的位置」

也就是说：

能进 queue ⇒ 一定是 '0'

BFS 不是“试跳”

而是 扩展可达区间

5️⃣ 为什么不需要 DFS / DP？

DFS：会重复走区间，难剪枝

DP：本质还是区间转移，离不开 BFS 思想

BFS + farthest：

自然处理“层次扩展”

更直观、更好优化

👉 这是一个 BFS 问题，不是贪心

6️⃣ 时间 & 空间复杂度
时间复杂度
O(n)


原因：

每个 index：

最多入队一次

最多被扫描一次

空间复杂度
O(n)


visited 数组

queue

7️⃣ 面试官最爱追问的 3 个点
Q1：farthest 为什么不会漏解？

因为每个区间只向右扩展
后面的 i 不可能跳到比前面更靠左的地方

Q2：为什么一开始判断 s[-1] == '1'？

终点不能站，直接 false
是一个 cheap but important 的剪枝

Q3：能不能不用 visited？

可以
直接把 s[j] = '1' 当作“已访问”
思路不变

8️⃣ 一句话终极记忆版（强烈推荐）

Jump Game VII = BFS + 区间扫描
farthest 用来保证每个位置只被扫描一次
queue 存的是“已经能站到的位置”

LC 2297. Jump Game VIII

跳跃规则转化为单调栈维护，是单调栈 + DP 的高级应用！

Jump Game VIII 完整总结

题目核心
目标：从索引 0 跳到索引 n-1，求最小代价
跳跃规则：从位置 i 跳到位置 j（i < j），满足以下两种情况之一：
跳跃类型高度条件中间元素条件形象理解向上跳nums[i] ≤ nums[j]中间所有 nums[k] < nums[i]爬山，中间不能有更高的峰向下跳nums[i] > nums[j]中间所有 nums[k] ≥ nums[i]滑坡，中间不能有凹陷

解题思路演进
1️⃣ 暴力 DP（会超时）
python# O(n³) - 太慢
for i in range(n):
    for j in range(i+1, n):
        # 检查能否从i跳到j
        if can_jump(i, j):  # O(n) 检查中间元素
            dp[j] = min(dp[j], dp[i] + costs[j])
问题：每次都要遍历中间元素验证条件

2️⃣ 单调栈优化（通过）
核心思想：反向思考

❌ 不问："从 i 能跳到哪？"
✅ 而问："谁能跳到 i？"

单调栈的作用：

维护候选起点
自动验证中间元素条件
弹出时就是合法跳跃

python# O(n) - 每个元素最多入栈出栈各1次
for i in range(n):
    # 递增栈处理向上跳
    while inc_stack and nums[inc_stack[-1]] <= nums[i]:
        j = inc_stack.pop()
        dp[i] = min(dp[i], dp[j] + costs[i])

    # 递减栈处理向下跳
    while dec_stack and nums[dec_stack[-1]] > nums[i]:
        j = dec_stack.pop()
        dp[i] = min(dp[i], dp[j] + costs[i])

    inc_stack.append(i)
    dec_stack.append(i)
```

---

## 单调栈工作原理

### 递增栈（处理向上跳）

**维护的序列**：
```
栈底 → 栈顶：值递减
inc_stack = [i1, i2, i3]
栈内值 = [大, 中, 小]
```

**弹出规则**：当 `nums[栈顶] ≤ nums[当前]`

**自动保证**：
- ✅ 高度条件：`nums[弹出元素] ≤ nums[当前]`
- ✅ 中间元素：栈的递减性质 → 中间元素都 < 起点

**例子**：
```
nums = [5, 3, 2, 6]
栈变化：
i=0: [0]    值=[5]
i=1: [0,1]  值=[5,3]     (3<5, 不弹出)
i=2: [0,1,2] 值=[5,3,2]  (2<3, 不弹出)
i=3: 弹出2 → 2可以跳到3 (2≤6 ✅, 中间无)
     弹出1 → 1可以跳到3 (3≤6 ✅, 中间2<3 ✅)
     弹出0 → 0可以跳到3 (5≤6 ✅, 中间1,2都<5 ✅)
```

---

### 递减栈（处理向下跳）

**维护的序列**：
```
栈底 → 栈顶：值递增
dec_stack = [i1, i2, i3]
栈内值 = [小, 中, 大]
```

**弹出规则**：当 `nums[栈顶] > nums[当前]`

**自动保证**：
- ✅ 高度条件：`nums[弹出元素] > nums[当前]`
- ✅ 中间元素：栈的递增性质 → 中间元素都 ≥ 起点

**例子**：
```
nums = [2, 5, 7, 3]
栈变化：
i=0: [0]    值=[2]
i=1: [0,1]  值=[2,5]     (2<5, 不弹出)
i=2: [0,1,2] 值=[2,5,7]  (5<7, 不弹出)
i=3: 弹出2 → 2可以跳到3 (7>3 ✅, 中间无)
     弹出1 → 1可以跳到3 (5>3 ✅, 中间7≥5 ✅)
     不弹0 → (2<3, 不满足向下跳)

为什么单调栈有效？
传统暴力验证
python# 检查从i能否跳到j
for k in range(i+1, j):
    if 向上跳 and nums[k] >= nums[i]:
        return False  # 有障碍
    if 向下跳 and nums[k] < nums[i]:
        return False  # 有凹陷
```

### 单调栈隐式验证

| 检查项 | 单调栈如何保证 |
|--------|--------------|
| 高度条件 | 弹出条件就是高度条件 |
| 中间元素 | **栈的单调性**自动满足 |

**核心洞察**：
```
递增栈：栈底→栈顶递减
→ 后面的元素比前面小
→ 中间元素 < 起点 ✅

递减栈：栈底→栈顶递增
→ 后面的元素比前面大
→ 中间元素 ≥ 起点 ✅



You are given a 0-indexed integer array nums of length n. You are initially standing at index 0. You can jump from index i to index j where i < j if:

nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j, or
nums[i] > nums[j] and nums[k] >= nums[i] for all indexes k in the range i < k < j.
You are also given an integer array costs of length n where costs[i] denotes the cost of jumping to index i.

Return the minimum cost to jump to the index n - 1.



Example 1:

Input: nums = [3,2,4,4,1], costs = [3,7,6,4,2]
Output: 8
Explanation: You start at index 0.
- Jump to index 2 with a cost of costs[2] = 6.
- Jump to index 4 with a cost of costs[4] = 2.
The total cost is 8. It can be proven that 8 is the minimum cost needed.
Two other possible paths are from index 0 -> 1 -> 4 and index 0 -> 2 -> 3 -> 4.
These have a total cost of 9 and 12, respectively.
Example 2:

Input: nums = [0,1,2], costs = [1,1,1]
Output: 2
Explanation: Start at index 0.
- Jump to index 1 with a cost of costs[1] = 1.
- Jump to index 2 with a cost of costs[2] = 1.
The total cost is 2. Note that you cannot jump directly from index 0 to index 2 because nums[0] <= nums[1].

1. class Solution:
   
2.     def minCost(self, nums: List[int], costs: List[int]) -> int:
   
3.         n = len(nums)
   
4.         
   
5.         # dp[i] = 到达位置i的最小cost
   
6.         dp = [float('inf')] * n
   
7.         dp[0] = 0  # 起点cost为0
   
8.         
   
9.         # 递增栈：找向上跳的目标（nums[j] >= nums[i]）
   
10.         inc_stack = []
    
11.         # 递减栈：找向下跳的目标（nums[j] < nums[i]）
    
12.         dec_stack = []
    
13.         
    
14.         for i in range(n):
    
15.             # 处理递增栈：从栈中弹出所有 <= nums[i] 的元素
    
16.             # 这些元素可以向上跳到i
    
17.             while inc_stack and nums[inc_stack[-1]] <= nums[i]:
    
18.                 j = inc_stack.pop()
    
19.                 dp[i] = min(dp[i], dp[j] + costs[i])
    
20.             
    
21.             # 处理递减栈：从栈中弹出所有 > nums[i] 的元素
    
22.             # 这些元素可以向下跳到i
    
23.             while dec_stack and nums[dec_stack[-1]] > nums[i]:
    
24.                 j = dec_stack.pop()
    
25.                 dp[i] = min(dp[i], dp[j] + costs[i])
    
26.             
    
27.             # 将当前索引加入两个栈
    
28.             inc_stack.append(i)
    
29.             dec_stack.append(i)
    
30.         
    
31.         return dp[-1]

复制代码

补充上单调栈的结论，

非常好的问题！让我详细分析这个情况。

---

## 简短回答

**会出现！** 而且这正是单调栈的核心机制。

---

## 详细解释

### 情况分析

```python
while inc_stack and nums[inc_stack[-1]] <= nums[i]:
    j = inc_stack.pop()
    dp[i] = min(dp[i], dp[j] + costs[i])

# while 循环结束后
inc_stack.append(i)
```

**while 循环结束时，有两种可能**：

#### 情况1：栈空了
```python
inc_stack = []  # 空栈
# 所有元素都被弹出了
```

#### 情况2：栈不空，但 `nums[inc_stack[-1]] > nums[i]`
```python
inc_stack = [某些索引]
# 栈顶元素的值 > nums[i]
```

---

## 具体例子

`nums = [5, 3, 2, 6, 4]`

### 逐步演示

#### i = 0
```python
inc_stack = []
操作：加入0
inc_stack = [0]
栈内值 = [5]
```

#### i = 1
```python
检查：nums[0]=5 ≤ nums[1]=3？
答案：5 > 3，❌ 不满足，while循环不执行

inc_stack = [0, 1]
栈内值 = [5, 3]  ← 注意！5 > 3
```

**这里就出现了 `nums[inc_stack[-1]] > nums[i]` 的情况！**

#### i = 2
```python
检查：nums[1]=3 ≤ nums[2]=2？
答案：3 > 2，❌ 不满足

inc_stack = [0, 1, 2]
栈内值 = [5, 3, 2]  ← 递减序列
```

#### i = 3（关键时刻）
```python
检查：nums[2]=2 ≤ nums[3]=6？✅
弹出2，更新 dp[3]

检查：nums[1]=3 ≤ nums[3]=6？✅
弹出1，更新 dp[3]

检查：nums[0]=5 ≤ nums[3]=6？✅
弹出0，更新 dp[3]

inc_stack = []  ← 栈空了
```

#### i = 4
```python
inc_stack = []，while 不执行

inc_stack = [4]
栈内值 = [4]
```

---

## 为什么会出现这种情况？

### 递增栈的真实含义

```python
inc_stack 维护的不是"递增序列"
而是"还没找到向上跳目标的候选起点"
```

**栈内值的特点**：
```
栈底 → 栈顶：值递减

inc_stack = [i1, i2, i3]
栈内值 = [大, 中, 小]
```

### 为什么是递减？

因为：
- 如果后面的元素 ≥ 前面的元素，前面的就会被弹出
- 只有**更小的元素**才能留在栈里

---

## 图解说明

```
nums = [5, 3, 2, 6, 4]
索引:   0  1  2  3  4

过程：
         5
        /
       3
      /
     2
    ↑
    |
这些都没找到"向上跳"的目标

当6出现：
         6  ← 新元素
        /|\
       / | \
      2  3  5  ← 全部弹出！
      
因为 2≤6, 3≤6, 5≤6 都满足向上跳条件

当4出现：
     6
      \
       4  ← 6 > 4，不弹出
      
inc_stack = [3, 4]
栈内值 = [6, 4]  ← 6 > 4，递减！
```

---

## 完整示例追踪

`nums = [7, 3, 5, 2, 8]`

| i | nums[i] | while 执行情况 | inc_stack（操作后）| 栈内值 | 栈顶 > nums[i]? |
|---|---------|---------------|-------------------|--------|----------------|
| 0 | 7 | 栈空，不执行 | [0] | [7] | - |
| 1 | 3 | 7 > 3，不弹出 | [0,1] | [7,3] | ✅ 是的！7>3 |
| 2 | 5 | 3≤5，弹出1<br>7>5，不弹出 | [0,2] | [7,5] | ✅ 是的！7>5 |
| 3 | 2 | 5>2，不弹出 | [0,2,3] | [7,5,2] | ✅ 是的！5>2 |
| 4 | 8 | 2≤8，弹出3<br>5≤8，弹出2<br>7≤8，弹出0 | [4] | [8] | ❌ 栈空了 |

---

## 这种情况的意义

### 当 `nums[栈顶] > nums[i]` 时，表示：

```
栈顶元素"还没找到"能向上跳的目标
因为当前元素 nums[i] 比它小
```

**这是正常现象！**

---

## 三种可能的 while 循环结果

```python
while inc_stack and nums[inc_stack[-1]] <= nums[i]:
    j = inc_stack.pop()
    dp[i] = min(dp[i], dp[j] + costs[i])
```

| 结果 | 含义 | 例子 |
|------|------|------|
| **栈空了** | 所有元素都能跳到i | nums=[3,2,1,5], i=3 |
| **栈顶 > nums[i]** | 有些元素不能跳到i | nums=[5,3,2], i=2 |
| **栈顶 = nums[i]** | 相等时也弹出（因为≤） | nums=[3,3], i=1 |

---

## 代码逻辑总结

```python
# 向上跳的完整逻辑
while inc_stack and nums[inc_stack[-1]] <= nums[i]:
    # 这些元素能向上跳到i
    j = inc_stack.pop()
    dp[i] = min(dp[i], dp[j] + costs[i])

# while 结束后可能：
# 1. inc_stack 为空 → 所有元素都能跳到i
# 2. nums[inc_stack[-1]] > nums[i] → 栈顶元素不能跳到i

inc_stack.append(i)  # i成为新的候选起点
```

---

## 最终答案

**是的，会出现 `nums[inc_stack[-1]] > nums[i]` 的情况！**

这种情况表示：
- ✅ 栈顶元素**不能**向上跳到当前位置i
- ✅ 当前位置i会被加入栈，成为新的候选起点
- ✅ 栈内保持**递减序列**（大→小）

**这正是单调栈的精髓！** 栈维护的是"还没找到目标"的候选元素，而不是"单调递增"的值序列。

## 为什么会出现这种情况？

### 递增栈的真实含义

```python
inc_stack 维护的不是"递增序列"
而是"还没找到向上跳目标的候选起点"
```

**栈内值的特点**：
```
栈底 → 栈顶：值递减

inc_stack = [i1, i2, i3]
栈内值 = [大, 中, 小]
```

### 为什么是递减？

因为：
- 如果后面的元素 ≥ 前面的元素，前面的就会被弹出
- 只有**更小的元素**才能留在栈里

---

## 图解说明

```
nums = [5, 3, 2, 6, 4]
索引:   0  1  2  3  4

过程：
         5
        /
       3
      /
     2
    ↑
    |
这些都没找到"向上跳"的目标

当6出现：
         6  ← 新元素
        /|\
       / | \
      2  3  5  ← 全部弹出！
      
因为 2≤6, 3≤6, 5≤6 都满足向上跳条件

当4出现：
     6
      \
       4  ← 6 > 4，不弹出
      
inc_stack = [3, 4]
栈内值 = [6, 4]  ← 6 > 4，递减！
```

---

## 完整示例追踪

`nums = [7, 3, 5, 2, 8]`

| i | nums[i] | while 执行情况 | inc_stack（操作后）| 栈内值 | 栈顶 > nums[i]? |
|---|---------|---------------|-------------------|--------|----------------|
| 0 | 7 | 栈空，不执行 | [0] | [7] | - |
| 1 | 3 | 7 > 3，不弹出 | [0,1] | [7,3] | ✅ 是的！7>3 |
| 2 | 5 | 3≤5，弹出1<br>7>5，不弹出 | [0,2] | [7,5] | ✅ 是的！7>5 |
| 3 | 2 | 5>2，不弹出 | [0,2,3] | [7,5,2] | ✅ 是的！5>2 |
| 4 | 8 | 2≤8，弹出3<br>5≤8，弹出2<br>7≤8，弹出0 | [4] | [8] | ❌ 栈空了 |

---

## 这种情况的意义

### 当 `nums[栈顶] > nums[i]` 时，表示：

```
栈顶元素"还没找到"能向上跳的目标
因为当前元素 nums[i] 比它小
```

**这是正常现象！**

---

## 三种可能的 while 循环结果

```python
while inc_stack and nums[inc_stack[-1]] <= nums[i]:
    j = inc_stack.pop()
    dp[i] = min(dp[i], dp[j] + costs[i])
```

| 结果 | 含义 | 例子 |
|------|------|------|
| **栈空了** | 所有元素都能跳到i | nums=[3,2,1,5], i=3 |
| **栈顶 > nums[i]** | 有些元素不能跳到i | nums=[5,3,2], i=2 |
| **栈顶 = nums[i]** | 相等时也弹出（因为≤） | nums=[3,3], i=1 |

---

## 代码逻辑总结

```python
# 向上跳的完整逻辑
while inc_stack and nums[inc_stack[-1]] <= nums[i]:
    # 这些元素能向上跳到i
    j = inc_stack.pop()
    dp[i] = min(dp[i], dp[j] + costs[i])

# while 结束后可能：
# 1. inc_stack 为空 → 所有元素都能跳到i
# 2. nums[inc_stack[-1]] > nums[i] → 栈顶元素不能跳到i

inc_stack.append(i)  # i成为新的候选起点
```

---

## 最终答案

**是的，会出现 `nums[inc_stack[-1]] > nums[i]` 的情况！**

这种情况表示：
- ✅ 栈顶元素**不能**向上跳到当前位置i
- ✅ 当前位置i会被加入栈，成为新的候选起点
- ✅ 栈内保持**递减序列**（大→小）

**这正是单调栈的精髓！** 栈维护的是"还没找到目标"的候选元素，而不是"单调递增"的值序列。

LC 3379. Transformed Array

1. class Solution:
   
2.     def constructTransformedArray(self, nums: List[int]) -> List[int]:
   
3.         
   
4.         n = len(nums)
   
5.         results = [0] * n
   
6. 
   
7.         for i in range(n):
   
8.             if nums[i] != 0:
   
9.                 new_ind =  (i + nums[i]) % n
   
10.                 results[i] = nums[new_ind]
    
11.             else:
    
12.                 results[i] = nums[i]
    
13. 
    
14.         return results        

复制代码

Python 的取模结果，符号永远和 b（除数）一致

在 Python 里，a % b 的结果确实取决于 b（除数）的正负号。

这是很多语言里最容易踩坑的地方之一。

一句话结论（先记住）

Python 的取模结果，符号永远和 b（除数）一致

Python 对 % 的“官方定义”

Python 里，a % b 定义为：

a % b = a - b * floor(a / b)


注意关键点：
👉 用的是 floor 向下取整（不是截断）

举几个最直观的例子
1️⃣ b > 0（最常见）
5 % 3  = 2
-5 % 3 = 1


解释：

-5 = (-2)*3 + 1

结果 1 是 非负的

✅ 结果 ∈ [0, b-1]

2️⃣ b < 0（容易懵的）
5 % -3  = -1
-5 % -3 = -2


解释：

5 = (-1)*(-3) + (-1)

-5 = (1)*(-3) + (-2)

✅ 结果是 非正的

统一对比表（很重要）
表达式        结果
5 % 3        2
-5 % 3        1
5 % -3        -1
-5 % -3        -2

你会发现：

👉 结果永远和 b 同号

和 C / Java 的区别（面试高频）
语言        % 结果符号
Python        和 除数 b 同号
C / C++ / Java        和 被除数 a 同号

例如在 C 里：

-5 % 3 == -2


但在 Python 里：

-5 % 3 == 1


⚠️ 这点在跨语言写算法时非常关键

算法里什么时候要特别小心？
✅ 循环数组 / 下标安全

Python 很友好：

(i - 1) % n


即使 i = 0，也会得到：

(0 - 1) % 5 == 4


👉 不会越界

这也是为什么 Python 写环形数组特别爽。

LC 46. Permutations

核心思路
回溯三要素：

选择：每次从剩余元素中选一个
约束：不能重复选择已使用的元素
目标：当选够 n 个元素时，得到一个排列

回溯算法的本质：

穷举所有可能的解
通过剪枝提高效率
做选择 → 递归 → 撤销选择

全排列是回溯算法的经典应用，掌握它就掌握了回溯的核心思想！

1. class Solution:
   
2.     def permute(self, nums: List[int]) -> List[List[int]]:
   
3.         res = []  # 存储所有排列的结果
   
4.         n = len(nums)
   
5. 
   
6.         def backTrack(path, used):
   
7.             """
   
8.             回溯函数：生成所有排列
   
9.             
   
10.             参数：
    
11.                 path: 当前已选择的元素路径（当前排列）
    
12.                 used: 布尔数组，标记哪些元素已被使用
    
13.             """
    
14.             
    
15.             # === 递归终止条件 ===
    
16.             # 当路径长度等于数组长度时，说明找到了一个完整的排列
    
17.             if len(path) == n:
    
18.                 res.append(path.copy())  # ⚠️ 必须复制！否则后续修改会影响结果
    
19.                 return
    
20.             
    
21.             # === 遍历所有可能的选择 ===
    
22.             for i in range(n):
    
23.                 # --- 剪枝：跳过已使用的元素 ---
    
24.                 if used[i]:
    
25.                     continue
    
26.                
    
27.                 # === 第1步：做选择 ===
    
28.                 path.append(nums[i])  # 将当前元素加入路径
    
29.                 used[i] = True        # 标记为已使用
    
30.                
    
31.                 # === 第2步：递归探索 ===
    
32.                 # 进入下一层决策树，继续选择下一个元素
    
33.                 backTrack(path, used)
    
34.                
    
35.                 # === 第3步：撤销选择（回溯）===
    
36.                 # 从路径中移除，恢复到选择前的状态
    
37.                 path.pop()            # 移除刚才添加的元素
    
38.                 used[i] = False       # 标记为未使用，释放给其他分支使用
    
39.                 # 💡 这一步是关键！让元素可以在其他排列中被使用
    
40. 
    
41.         # === 启动回溯 ===
    
42.         # 初始状态：空路径，所有元素都未使用
    
43.         backTrack([], [False] * n)
    
44. 
    
45.         return res  # 返回所有排列

复制代码