刷题记录帖子

560. Subarray Sum Equals K

1. class Solution:
   
2.     def subarraySum(self, nums: List[int], k: int) -> int:
   
3.         """
   
4.         preSum = [0] * (len(nums) + 1)
   
5. 
   
6.         for i in range(len(nums)): preSum[i+1] = preSum[i] + nums[i]
   
7.         
   
8.         ans = 0
   
9.         for i in range(0, len(nums)+1):
   
10.             for j in range(i+1, len(nums)+1):
    
11.                 if preSum[j] - preSum[i] == k: ans += 1
    
12.         return ans
    
13.         """
    
14.         currSum = 0
    
15.         preSum = collections.defaultdict(int)
    
16.         preSum[0] = 1
    
17.         ans = 0
    
18. 
    
19.         for num in nums:
    
20.             currSum += num
    
21.             if currSum - k in preSum:
    
22.                 ans += preSum[currSum - k]
    
23.             preSum[currSum] += 1
    
24. 
    
25.         return ans
    
26. 
    

复制代码

好，这一题是 **“Subarray Sum Equals K（和为 K 的子数组个数）”** 的经典解法。
我用 **直觉 → 数学关系 → 哈希表怎么用 → 走一遍例子** 来给你彻底讲清楚。

---

## 一、问题一句话版

给你一个数组 `nums` 和一个整数 `k`，
**问：有多少个连续子数组的和等于 `k`？**

---

## 二、核心直觉（这一步最重要）

### 定义前缀和

令：

```
sum[i] = nums[0] + nums[1] + ... + nums[i]
```

那么区间 `(j+1 ... i)` 的和是：

```
sum[i] - sum[j]
```

---

## 三、关键数学结论（题解里的那段话）

### 1️⃣ 为什么「前缀和相等 → 中间和为 0」

如果：

```
sum[i] == sum[j]
```

那么：

```
sum[i] - sum[j] = 0
```

👉 `j+1` 到 `i` 的子数组和为 **0**

---

### 2️⃣ 推广到一般情况（真正用到的）

如果：

```
sum[i] - sum[j] = k
```

等价于：

```
sum[j] = sum[i] - k
```

👉 **只要之前出现过 `sum[i] - k`，就说明存在一个子数组和为 `k`，并且以 `i` 结尾**

---

## 四、HashMap 在这里干什么？

我们用一个 hashmap（字典）：

```
map[前缀和] = 出现次数
```

它的作用是：

> 快速告诉我：
> **“到目前为止，有多少个前缀和等于某个值”**

---

## 五、算法流程（一步一步）

### 初始化

```python
count = 0
curr_sum = 0
map = {0: 1}
```

⚠️ `0:1` 很关键：

* 表示「在数组开始前，有一个前缀和为 0」
* 这样可以正确处理 **从下标 0 开始的子数组**

---

### 遍历数组

对每个 `num`：

1. 更新前缀和

   ```python
   curr_sum += num
   ```

2. 看有没有 `curr_sum - k`

   ```python
   if curr_sum - k in map:
       count += map[curr_sum - k]
   ```

3. 把当前前缀和加入 hashmap

   ```python
   map[curr_sum] += 1
   ```

---

## 六、为什么要「出现次数」，而不是 True / False？

因为：

> **同一个前缀和可能出现多次**

每出现一次：

* 都代表一个不同的起点
* 都能形成一个新的子数组

---

## 七、完整走一遍例子（非常关键）

### 示例

```python
nums = [1, 2, 3]
k = 3
```

---

### 初始状态

```
map = {0:1}
curr_sum = 0
count = 0
```

---

### i = 0, num = 1

```
curr_sum = 1
curr_sum - k = -2 → 不存在
map = {0:1, 1:1}
```

---

### i = 1, num = 2

```
curr_sum = 3
curr_sum - k = 0 → map[0] = 1
count += 1
```

子数组：

```
[1,2]
```

更新 map：

```
map = {0:1, 1:1, 3:1}
```

---

### i = 2, num = 3

```
curr_sum = 6
curr_sum - k = 3 → map[3] = 1
count += 1
```

子数组：

```
[3]
```

---

### 最终结果

```
count = 2
```

---

## 八、为什么这是 O(n)？

* 每个元素 **只遍历一次**
* hashmap 查询是 **O(1)**

相比暴力解法：

| 方法            | 时间复杂度    |
| ------------- | -------- |
| 三重循环          | O(n³)    |
| 前缀和 + 双循环     | O(n²)    |
| 前缀和 + HashMap | **O(n)** |

---

## 九、一句话总结（面试必背）

> 通过前缀和，把「子数组和为 k」转化为
> 查找是否存在 `sum[i] - k`，
> 使用 HashMap 记录前缀和出现次数，
> 从而在 O(n) 时间内完成统计。

---


这个问题问得**非常到位**，基本就是这道题的“分水岭理解点”。我直接给你一个**清晰对比 + 直觉解释**。

---

## 一、先说结论（一句话版）

> **前缀和 + HashMap 能处理负数，是因为它不依赖“区间和的单调性”；
> 滑动窗口不行，是因为一旦有负数，窗口和就不再单调变化。**

下面展开。

---

## 二、滑动窗口为什么在「全正数」时可行？

滑动窗口隐含了一个**关键假设**：

* 右指针右移 → 区间和 **只会变大**
* 左指针右移 → 区间和 **只会变小**

这个假设 **只在所有数 ≥ 0 时成立**。

### 典型逻辑

```text
sum < k  → 扩大窗口（right++）
sum > k  → 缩小窗口（left++）
```

这是一个“**可控的单调过程**”。

---

## 三、负数一出现，滑动窗口就崩了 💥

### 举个最小反例

```
nums = [1, -1, 1]
k = 1
```

---

### 滑动窗口尝试

1️⃣ `left=0, right=0`

```
sum = 1 ✔
```

2️⃣ 扩展窗口

```
right=1
sum = 0   （变小了！）
```

3️⃣ 再扩展

```
right=2
sum = 1 ✔
```

现在问题来了：

* `sum < k` 时你 **不知道** 是该扩右还是缩左
* `sum > k` 时缩左 **也可能让 sum 变大**

👉 **决策方向不再可靠**

---

### 本质问题

> 有负数时，
> **移动指针 ≠ 可预测地改变区间和**

滑动窗口失去了“导航能力”。

---

## 四、前缀和 + HashMap 为什么不怕负数？

### 它根本不「移动窗口」

它做的是：

> **固定右端点 i，回头看所有可能的左端点 j**

数学关系：

```
sum[i] - sum[j] = k
```

⇔

```
sum[j] = sum[i] - k
```

---

### 负数完全不影响这个等式

无论 nums 里是：

```
+5, -3, +10, -8, ...
```

这个关系 **永远成立**。

---

## 五、一个负数示例完整走一遍

```
nums = [1, -1, 1]
k = 1
```

### 过程

| i | num | curr_sum | curr_sum - k | map       | 新增子数组    |
| - | --- | -------- | ------------ | --------- | -------- |
| - | -   | 0        | -            | {0:1}     | -        |
| 0 | 1   | 1        | 0            | {0:1}     | [1]      |
| 1 | -1  | 0        | -1           | {0:1,1:1} | -        |
| 2 | 1   | 1        | 0            | {0:2,1:1} | [1,-1,1] |

👉 完全不需要任何“回退”或“调整窗口”。

---

## 六、对比总结（核心差异）

| 维度      | 滑动窗口 | 前缀和 + HashMap |
| ------- | ---- | ------------- |
| 是否依赖单调性 | 是    | 否             |
| 能否处理负数  | ❌    | ✅             |
| 思维方式    | 移动区间 | 数学等式          |
| 本质      | 贪心   | 计数 / 统计       |

---

## 七、什么时候该用哪种？

### 用滑动窗口的前提

* 数组元素 **全是非负**
* 或满足某种 **单调性质**

👉 例如：

* 最小子数组和 ≥ k
* 不重复字符的最长子串

---

### 用前缀和 + HashMap 的信号

* 出现 **负数**
* 问的是 **子数组个数**
* 和、差、等于某个值

👉 **90% 都是前缀和 + 哈希**

---

## 八、一句话终极总结（面试杀手锏）

> 滑动窗口依赖区间和的单调变化，一旦有负数就失效；
> 前缀和方法基于恒等式 `sum[i] - sum[j] = k`，与元素正负无关，因此能稳定处理负数。

875. Koko Eating Bananas

1. class Solution:
   
2.     def minEatingSpeed(self, piles: List[int], h: int) -> int:
   
3.         """
   
4.         given k, how to check if k is possible.
   
5. 
   
6.         shall be sum( ceil(piles/k)) < h
   
7. 
   
8.         k >= 1
   
9. 
   
10.         k < max(piles)
    
11. 
    
12.         binnary search
    
13.         """
    
14.         def canFinish(k, h):
    
15.             total_time = 0
    
16.             for p in piles:
    
17.                 total_time += math.ceil(p/k)
    
18.             if total_time <= h: return True
    
19.             else: return False
    
20. 
    
21.         left = 1
    
22.         right = max(piles)
    
23. 
    
24.         while left < right:
    
25.             mid = (left + right) // 2
    
26.             if canFinish(mid, h):
    
27.                 right = mid
    
28.             else:
    
29.                 left = mid + 1
    
30.         return left
    
31. 
    
32. 
    
33.         

复制代码

好，这个表你**背下来基本就不怕二分了**。我给你一张**「三种二分模板对照表」**，每一行都是**决策级信息**，不是空话。

---

## 一、三种二分模板总览（先看这张）

| 模板类型     | 要找的东西       | 条件函数形态          | 典型题目                   |
| -------- | ----------- | --------------- | ---------------------- |
| **模板 A** | 最小的 True    | F F F **T T T** | Koko、Capacity、Min Days |
| **模板 B** | 最大的 True    | T T T **F F F** | 最大可行值                  |
| **模板 C** | 精确等于 target | 排好序数组           | 标准二分                   |

---

## 二、模板 A：找「最小可行值」（你这题用的）

### 适用场景

* 问：**minimum / smallest**
* 条件函数是 **单调递增**
* 形态：`False → True`

### 区间含义

> `[left, right]` **一定包含答案**

### 模板代码（推荐背）

```python
left = L
right = R

while left < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1

return left
```

### 关键记忆点

* `mid` 偏左
* `right = mid`（保留答案）
* **return left**

---

## 三、模板 B：找「最大可行值」

### 适用场景

* 问：**maximum / largest**
* 条件函数是 **单调递减**
* 形态：`True → False`

### 区间含义

> `[left, right]` **一定包含答案**

### 模板代码

```python
left = L
right = R

while left < right:
    mid = (left + right + 1) // 2  # 向右取中点
    if check(mid):
        left = mid
    else:
        right = mid - 1

return left
```

### 关键记忆点

* `mid` 偏右（防死循环）
* `left = mid`（保留答案）
* **return left**

---

## 四、模板 C：标准二分（找某个具体值）

### 适用场景

* **数组已排序**
* 找某个 target 是否存在 / 下标

### 模板代码

```python
left = 0
right = n - 1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

return -1
```

### 关键记忆点

* `left <= right`
* 区间是 **闭区间**
* 找不到返回 -1

---

## 五、三种模板「最容易混淆点」对照

| 维度       | 模板 A           | 模板 B            | 模板 C            |
| -------- | -------------- | --------------- | --------------- |
| while 条件 | `left < right` | `left < right`  | `left <= right` |
| mid 取值   | `(l+r)//2`     | `(l+r+1)//2`    | `(l+r)//2`      |
| True 时   | `right = mid`  | `left = mid`    | return          |
| False 时  | `left = mid+1` | `right = mid-1` | 移边界             |
| 返回       | `left`         | `left`          | index           |

---

## 六、怎么 3 秒判断该用哪个模板？

问自己这 3 个问题：

1. 我是不是在 **“选一个数”**？

   * 否 → 模板 C
2. 我是不是在找 **最小 / 最大**？

   * 是 → A 或 B
3. `check(x)` 是不是单调？

   * False→True → 模板 A
   * True→False → 模板 B

---

## 七、一句话终极口诀（建议背）

> 最小 True 用 A，
> 最大 True 用 B，
> 排序找数用 C。

456. 132 Pattern

1. class Solution:
   
2.     def find132pattern(self, nums: List[int]) -> bool:
   
3.         """
   
4.         the key is to find j, j needs to be largest
   
5.         j > i, can be easily do, do one round to find preMIN to track smallest i of left of j
   
6. 
   
7.         for right, the key is to find k, smaller than j but not too small, need to be large than i
   
8. 
   
9.         using monotonic stack
   
10. 
    
11.         for j from right to left:
    
12.             nums[j] > preMIN[i]: ## nums[j] > nums[i]
    
13.                 # update stack
    
14.                 remove smaller than preMIN j(k)
    
15.                 if found stack.top() < j: then stack.top is k
    
16.                     return True
    
17.             stack.push[nums[j]]
    
18. 
    
19.         """
    
20.         n = len(nums)
    
21.         preMIN = [0] * n
    
22.         currentMIN = float('inf')
    
23.         for i in range(n):
    
24.             if nums[i] < currentMIN:
    
25.                 currentMIN = nums[i]
    
26.                 preMIN[i] = nums[i]
    
27.             else:
    
28.                 preMIN[i] = currentMIN
    
29.         
    
30.         stack_k = []
    
31.         for j in range(n-1, 0, -1):
    
32.             if nums[j] > preMIN[j]:
    
33.                 # nums[j] > nums[i]
    
34.                 while stack_k and stack_k[-1] <= preMIN[j]:
    
35.                     # nums[k] > nums[i]
    
36.                     stack_k.pop()
    
37.                 if stack_k and stack_k[-1] < nums[j]:
    
38.                     #nums[j] > nums[k]
    
39.                     return True
    
40.                 stack_k.append(nums[j])
    
41.         return False
    
42.         

复制代码

XIaoMing 讲解的很清楚，不少别的解释说不清楚。【LeetCode 每日一题 Daily Challenge 456 132 Pattern】 https://www.bilibili.com/video/B ... 6911a1753da5ccb0521

其实就是找 j，然后 i 比较容易找， 找左侧最小的那个元素就行，这样给出最宽的 i，j，因为 k 一定在这个之间。

然后就是从右向左，用 stack 维持住 candidate-k, 然后对于 k 做检查，两个判断，

一，k 要比 i 大，这个和左侧最小值数组比较，如果不够就出栈。

二，k 要比 j 小，满足一的情况下，这个满足就可以返回 True 了。

LC 1116. Print Zero Even Odd 线程相关


Semaphore 是一个计数器，用来控制线程访问共享资源或执行顺序。
acquire() 拿许可证，计数减 1；release() 归还许可证，计数加 1。


下题，用 Zero 控制流程

1. from threading import Semaphore
   
2. from typing import Callable
   
3. 
   
4. class ZeroEvenOdd:
   
5.    def __init__(self, n: int):
   
6.        self.n = n
   
7.        # 初始化信号量
   
8.        self.sem_zero = Semaphore(1)  # zero 先执行
   
9.        self.sem_odd = Semaphore(0)
   
10.        self.sem_even = Semaphore(0)
    
11. 
    
12.    # printNumber(x) outputs "x", where x is an integer.
    
13.    def zero(self, printNumber: 'Callable[[int], None]') -> None:
    
14.        for i in range(1, self.n + 1):
    
15.            self.sem_zero.acquire()       # 等待 zero 信号
    
16.            printNumber(0)                # 打印 0
    
17.            if i % 2 == 1:
    
18.                self.sem_odd.release()    # 奇数下一个打印 odd
    
19.            else:
    
20.                self.sem_even.release()   # 偶数下一个打印 even
    
21. 
    
22.    def even(self, printNumber: 'Callable[[int], None]') -> None:
    
23.        for i in range(2, self.n + 1, 2):
    
24.            self.sem_even.acquire()       # 等待 even 信号
    
25.            printNumber(i)                # 打印偶数
    
26.            self.sem_zero.release()       # 打印完 0 下一个循环
    
27. 
    
28.    def odd(self, printNumber: 'Callable[[int], None]') -> None:
    
29.        for i in range(1, self.n + 1, 2):
    
30.            self.sem_odd.acquire()        # 等待 odd 信号
    
31.            printNumber(i)                # 打印奇数
    
32.            self.sem_zero.release()       # 打印完 0 下一个循环

复制代码

LC 232. Implement Queue using Stacks

1. class MyQueue:
   
2. 
   
3.     def __init__(self):
   
4.         self.top = None
   
5.         self.s1  = []
   
6.         self.s2  = []
   
7. 
   
8.     def push(self, x: int) -> None:
   
9.         self.s1.append(x)
   
10.         if len(self.s1) == 1: self.top = x
    
11. 
    
12.     def pop(self) -> int:
    
13.         while self.s1:
    
14.             curr = self.s1.pop(-1)
    
15.             self.s2.append(curr)
    
16.         if self.s2: ans = self.s2.pop(-1)
    
17.         else:
    
18.             self.top = None
    
19.             return
    
20.         if self.s2:
    
21.             self.top = self.s2[-1]
    
22.             while self.s2:
    
23.                 self.s1.append(self.s2.pop(-1))
    
24.         return ans
    
25. 
    
26.     def peek(self) -> int:
    
27.         return self.top
    
28.         
    
29. 
    
30.     def empty(self) -> bool:
    
31.         return len(self.s1) == 0
    
32. 
    
33. 
    
34. # Your MyQueue object will be instantiated and called as such:
    
35. # obj = MyQueue()
    
36. # obj.push(x)
    
37. # param_2 = obj.pop()
    
38. # param_3 = obj.peek()
    
39. # param_4 = obj.empty()

复制代码

Myron2017 发表于 2021-12-19 22:42
300. Longest Increasing Subsequence

经典题，NlgN 值得背诵

dp is also good

1. class Solution:
   
2.     def lengthOfLIS(self, nums: List[int]) -> int:
   
3.         # LIS ends at nums[i]
   
4.         dp = [1] * len(nums)
   
5.         
   
6.         for i in range(len(nums)):
   
7.             for j in range(0, i):
   
8.                 # if nums[i] > nums[j] = > dp[i] = dp[j]+1
   
9.                 # else: == > dp[i]
   
10.                 if nums[i] > nums[j]:
    
11.                     dp[i] = max(dp[j]+1, dp[i])
    
12.         return max(dp)

复制代码

857. Minimum Cost to Hire K Workers

关键能力，数学模型的抽象来解决问题。

需要抽象出，功能的最低工资，应该是 K 个人中最高的那个，那么为了总费用最小，就选最有性价比的。

但是这个不一定是最低的，因为可能有的工人效率高，虽然贵，但是一个人顶好几个，所以需要循环再判断。

1. class Solution:
   
2.     def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
   
3.         """
   
4.         quality: q[1], q[2], ...... q[n]
   
5.         wage:    w[1], w[2], ...... w[n]
   
6.         cost:    c[1], c[2], ...... c[n]
   
7.         c[i] >= c[i]
   
8. 
   
9.         r = c[i] / q[i]
   
10.         r = max(r[i])
    
11. 
    
12.         most expensive workers in group, enable this group
    
13.          r = w[i] / q[i]
    
14.         totalCost =  r * sum(q[i],... q[i+k-1])
    
15.         """
    
16.         n = len(quality)
    
17.         ratio = []
    
18.         total_q = 0
    
19. 
    
20.         for i in range(n):
    
21.             ratio.append((wage[i] / quality[i], quality[i]))
    
22.         ratio = sorted(ratio, key = lambda p: p[0])
    
23.         
    
24.         queue = []
    
25.         # first k worker as a first group
    
26.         for i in range(k):
    
27.             total_q += ratio[i][1]
    
28.             heapq.heappush(queue, -1 * ratio[i][1])
    
29.         totalCost = ratio[k-1][0] * total_q
    
30. 
    
31.         for i in range(k, n, 1):
    
32.             max_q = -1 * heapq.heappop(queue)
    
33.             if ratio[i][1] < max_q:
    
34.                 total_q = total_q - max_q + ratio[i][1]
    
35.                 totalCost = min(totalCost, total_q * ratio[i][0])
    
36.                 heapq.heappush(queue, -1 * ratio[i][1])
    
37.             else:
    
38.                 heapq.heappush(queue, -1 * max_q)
    
39. 
    
40.         return totalCost
    
41. 
    
42.         
    
43.         

复制代码

参考链接， https://www.youtube.com/watch?v=ISKLsPvXf3s

两题对照起来看，

209. Minimum Size Subarray Sum 这个没有负数， 所以更加简单， an array of positive integers nums and a positive integer target

直接移动窗口就行。

1. class Solution:
   
2.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
   
3.         l, r = 0, 0
   
4.         n = len(nums)
   
5.         currentWindowSum = 0
   
6.         ans = float('inf')
   
7. 
   
8.         for r in range(n):
   
9.             currentWindowSum += nums[r]
   
10.             while currentWindowSum >= target:
    
11.                 # move left and keep r, since left+1 to r must <= target since no negative
    
12.                 ans = min(ans, r - l + 1)
    
13.                 currentWindowSum -= nums[l]
    
14.                 l += 1
    
15. 
    
16.         if ans != float('inf') : return ans
    
17.         else: return 0

复制代码

更难的是这道题目， 862. Shortest Subarray with Sum at Least K

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k.

没说正负，例子给了负数，一定窗口失效，因为你移动窗口无法保证单调性。

The negative value -1 breaks the monotonic sum property that a standard sliding window relies on, making a simple variable-length sliding window approach unreliable.

好题，这道 **862. Shortest Subarray with Sum ≥ K** 的关键在于：
👉 **前缀和 + 单调队列（Monotonic Queue）**
因为数组里有 **负数**，普通滑动窗口会失效。

下面我按「为什么要这样做 → 每一步在干嘛 → 为什么是对的」来讲。

---

## 一、为什么需要前缀和？

定义前缀和：

```
preSum[i] = nums[0] + nums[1] + ... + nums[i-1]
```

这样任意子数组 `[l, r)` 的和就是：

```
sum(l, r) = preSum[r] - preSum[l]
```

问题就变成了：

> 找 **最短的 r - l**，使
> `preSum[r] - preSum[l] >= k`

---

## 二、队列里存的是什么？

队列 `q` 里存的是 **前缀和的下标**，不是值：

```
q = [i1, i2, i3, ...]
```

并且保持一个非常重要的性质：

> **preSum[q[0]] < preSum[q[1]] < preSum[q[2]] < ...**
> 👉 前缀和 **严格递增**

这就是「单调递增队列」。

---

## 三、核心思路一句话版

对每个 `i`（当作右端点）：

1. **从队尾**：
   把“没用的、更大的前缀和”删掉
2. **从队头**：
   尝试用当前 `i` 去更新最短答案
3. 把当前 `i` 放进队列

---

## 四、逐行解释代码里的两个 `while`

### 1️⃣ 为什么要「弹出队尾」？

```python
while q and preSum[q[-1]] >= preSum[i]:
    q.pop()
```

含义：
如果 **之前的前缀和 ≥ 当前前缀和**，那之前那个下标是“劣等的”。

为什么？

假设：

```
q[-1] < i
preSum[q[-1]] >= preSum[i]
```

以后对某个 `r`：

```
preSum[r] - preSum[i] >= preSum[r] - preSum[q[-1]]
```

而且：

* `i` 更靠右 → 子数组 **更短**
* 和还 **不更小**

👉 所以 `q[-1]` 永远不可能是最优左端点，直接丢掉。

---

### 2️⃣ 为什么要「弹出队头」并更新答案？

```python
while q and preSum[i] - preSum[q[0]] >= k:
    ans = min(ans, i - q[0])
    q.pop(0)
```

含义：
当前 `i` 作为右端点，**已经可以** 和队头形成合法子数组。

为什么可以安全地弹出？

* 队头 `q[0]` 是 **最小的前缀和**
* 对当前 `i` 来说，它给出了：

  * **最早**
  * **最短**
  * **第一次满足 ≥ k**

以后 `i` 只会变大：

* `i - q[0]` 只会更长
* 不可能再更优

👉 所以用完就扔。

---

## 五、完整流程（直觉版）

* 前缀和把「区间和」变成「差」
* 单调队列保证：

  * 左端点 **尽量靠右**
  * 前缀和 **尽量小**
* 每个下标 **只进队、出队一次**
* 时间复杂度：**O(n)**

---

## 六、用例 `[2, -1, 2], k = 3` 快速走一遍

```
nums     = [2, -1, 2]
preSum   = [0, 2, 1, 3]
index i  = 0  1  2  3
```

* i = 0 → q = [0]
* i = 1 → q = [0,1]
* i = 2 → preSum[1] >= preSum[2] → pop → q = [0,2]
* i = 3 → preSum[3] - preSum[0] = 3 ≥ 3
  → ans = 3 → pop 0

最终答案 = 3 ✅

---

## 七、一句话总结（面试可用）

> 这题用 **前缀和 + 单调递增队列**，
> 队列保证左端点的前缀和递增，
> 每次右端点扩展时：
>
> * 去掉无用的大前缀和
> * 尽量收缩左端点更新最短长度
>   从而在 **O(n)** 时间内解决包含负数的最短子数组问题。

这是这道题最核心、也最容易卡住的一点。 结论先给你：

不是“保证”，而是“我们强制维护” queue 为单调递增。

下面一步一步来，讲清楚「为什么一定能维护住」。

一、queue 单调递增指的是什么？
注意是 前缀和递增，不是下标递增（下标天然递增）。

preSum[q[0]] < preSum[q[1]] < preSum[q[2]] < ...
二、单调性的来源只有一行代码
👉 就是这一行：

while q and preSum[q[-1]] >= preSum[i]:
    q.pop()
这不是结果，这是手动维护的规则。

三、为什么这行代码一定能“修正”单调性？
假设一个坏情况（破坏单调）
队列尾部现在是：

... , j
而当前要加入 i，但：

preSum[j] >= preSum[i]
如果你 不删 j，队列就变成：

preSum[j] >= preSum[i]
➡️ 单调递增被破坏 ❌

那为什么可以安全地删掉 j？
这是关键逻辑。

对 任何未来的右端点 r（r > i）：

preSum[r] - preSum[i] >= preSum[r] - preSum[j]
并且：

i > j → 子数组更短
preSum[i] <= preSum[j] → 子数组和不更小
👉 i 在所有方面都“支配” j

所以：

j 永远不可能是最优左端点
留着它只会拖慢判断
删掉 j 不会丢失最优解

四、为什么删完之后，queue 就一定是单调的？
来看这个 while 的结构：

while q and preSum[q[-1]] >= preSum[i]:
    q.pop()
这会一直弹，直到：

preSum[q[-1]] < preSum[i]
然后我们才：

q.append(i)
所以新队列满足：

preSum[q[-1]] < preSum[i]
➡️ 单调递增性质 被恢复并保持

五、数学归纳法角度（更严谨）
初始状态
queue 为空 → 单调 ✔
归纳假设
假设在处理 i-1 后，queue 是单调递增的
处理第 i 个前缀和
不断删除尾部 ≥ preSum[i] 的元素
剩下的尾部 < preSum[i]
append(i)
➡️ 处理完 i 后，queue 仍然单调递增

归纳完成

六、为什么不用担心前面（queue front）破坏单调性？
注意：

q.pop(0)
这是 只删队头，不修改顺序：

a < b < c
删 a → b < c
👉 单调性天然保留

七、一句话面试级回答
queue 的单调递增性不是自然产生的，而是通过 while preSum[q[-1]] >= preSum[i] 主动删除被当前前缀和“支配”的下标来维护的。 每次加入新元素前都修正队尾，因此队列始终保持单调。

LC 3095. Shortest Subarray With OR at Least K I
      LC 3097. Shortest Subarray With OR at Least K II
Small size in I can use Brute Force, but the methods to write is also need to check

1. class Solution:
   
2.    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
   
3.        ans = float('inf')
   
4.        n = len(nums)
   
5.        for i in range(n):
   
6.            curr = 0 # 0 OR X = X
   
7.            for j in range(i, n):
   
8.                curr |= nums[j]
   
9.                if curr >= k:
   
10.                    ans = min(ans, j - i + 1)
    
11.                    break
    
12.        return -1 if ans == float('inf') else ans
    

复制代码

Large Size,

1. class Solution:
   
2.     def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
   
3.         n = len(nums)
   
4.         ans = float('inf')
   
5.         q = []  # 保存当前右端点的所有 OR 状态，每个元素是 (or_value, length)
   
6.         for x in nums:
   
7.             # nxt 用来保存当前元素 x 扩展后的新 OR 状态
   
8.             # 注意：每个 x 本身也可能构成长度为 1 的 special 子数组，所以先加入 (x,1)
   
9.             nxt = [(x, 1)]  # ✅ 修复了之前可能漏掉长度 1 子数组的问题
   
10.             # 遍历前一个右端点的 OR 状态，生成扩展后的 OR
    
11.             for val, length in q:
    
12.                 curr = val | x
    
13.                 # ❌ 之前你的 bug：检查了旧数组 q[-1][0]，而不是新的 nxt[-1][0]
    
14.                 #    这会导致重复 OR 值处理错误
    
15.                 # ✅ 修正：只检查 nxt[-1][0]
    
16.                 if curr == nxt[-1][0]:
    
17.                     # 如果重复 OR 值出现，只保留最短长度
    
18.                     nxt[-1] = (curr, min(length+1, nxt[-1][1]))
    
19.                 else:
    
20.                     # 否则直接添加新状态
    
21.                     nxt.append((curr, length+1))
    
22.             # 更新 q 为当前右端点的 OR 状态列表
    
23.             # ❌ 之前直接修改原数组可能导致遍历时状态混乱
    
24.             # ✅ 修正：用 nxt 临时数组再更新 q
    
25.             q = nxt
    
26.             # 遍历当前 OR 状态，更新答案
    
27.             for val, length in q:
    
28.                 if val >= k:
    
29.                     ans = min(length, ans)
    
30.         # 如果没有满足条件的子数组，返回 -1
    
31.         return ans if ans != float('inf') else -1
    

复制代码

问题重述
代码里写的是：
if nxt[-1][0] == new_or:
    # 相同 OR，只保留更短长度
    nxt[-1] = (new_or, min(nxt[-1][1], length + 1))
else:
    nxt.append((new_or, length + 1))
你问的是：为什么只检查 nxt[-1]？不需要遍历整个 nxt 数组吗？
关键点：OR 值是单调不减的
cur 存的 OR 状态是按“OR 值单调递增”生成的
你先把 (x,1) 放进 nxt。
然后遍历 cur：
每个 val | x 都 ≥ 上一个 new_or（因为 OR 只会增加 1，或者保持不变）。
所以 new_or 生成的顺序是非严格递增。
性质：
在遍历 cur 的过程中，如果出现重复 OR 值，只可能与 nxt 的最后一个元素重复。