刷题记录帖子

LC. 415. Add Strings

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.

You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.



Example 1:

Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:

Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"


Constraints:

1 <= num1.length, num2.length <= 104
num1 and num2 consist of only digits.
num1 and num2 don't have any leading zeros except for the zero itself.


我的解法

1. class Solution:
   
2.     def addStrings(self, num1: str, num2: str) -> str:
   
3.         ans = deque([])
   
4.         n1 = len(num1)
   
5.         n2 = len(num2)
   
6. 
   
7.         carry = 0
   
8.         ind1 = n1-1
   
9.         ind2 = n2-1
   
10. 
    
11.         while ind1 >= 0 and ind2 >= 0:
    
12.             dsum = int(num1[ind1]) + int(num2[ind2]) + carry
    
13.             ans.appendleft(str(dsum % 10))
    
14.             carry = dsum // 10
    
15.             ind1 -= 1
    
16.             ind2 -= 1
    
17. 
    
18.         while ind1 >= 0:
    
19.             dsum = int(num1[ind1]) + carry
    
20.             ans.appendleft(str(dsum % 10))
    
21.             carry = dsum // 10
    
22.             ind1 -= 1
    
23. 
    
24.         while ind2 >= 0:
    
25.             dsum = int(num2[ind2]) + carry
    
26.             ans.appendleft(str(dsum % 10))
    
27.             carry = dsum // 10
    
28.             ind2 -= 1
    
29.         
    
30.         if carry:
    
31.             ans.appendleft(str(carry))
    
32.         
    
33.         return "".join(ans)

复制代码

Gemini 的评价还挺中肯的

2. 你的代码可以怎样优化？ (Debug / 优化点)

你目前的写法是分了三个 while 循环：两个都没越界时。num1 没越界时。num2 没越界时。优化技巧：单循环合并我们完全可以把这三个循环合并成一个循环。只要 ind1 还没走完，或者 ind2 还没走完，或者最后还有进位 carry，我们就继续算。如果谁提前走完了，那个位置的数字就默认当做 0。


关于 int() 转换的严谨性：题目要求“不能直接把输入转成整数 (not convert the inputs to integers directly)”。你用 int(num1[ind1]) 转换的是单个字符，大多数面试官是可以接受的。但如果遇到极其严格的面试官（或者 C++/Java 背景的面试官），他们可能希望你连单个字符都不用内置强转。这时候可以使用 ASCII 码的偏移量来计算：ord(char) - ord('0')，这在 Python 中是 100% 符合“不依赖内置大数/转换库”要求的硬核写法。


关于 deque vs list：虽然 deque.appendleft() 是 $O(1)$，但在 Python 中，更常规且底层的执行效率更高的写法是：使用普通列表 list.append() 添加到尾部，最后一次性反转列表 ans[::-1]。因为普通列表的连续内存追加和切片反转在 CPython 底层优化得极其高效。

优化代码

1. class Solution:
   
2.     def addStrings(self, num1: str, num2: str) -> str:
   
3.         ans = []
   
4.         ind1, ind2 = len(num1) - 1, len(num2) - 1
   
5.         carry = 0
   
6. 
   
7.         while ind1 >= 0 or ind2 >= 0 or carry:
   
8.             # 严格模式：将字符转为数字
   
9.             x = ord(num1[ind1]) - ord('0') if ind1 >= 0 else 0
   
10.             y = ord(num2[ind2]) - ord('0') if ind2 >= 0 else 0
    
11.             
    
12.             total = x + y + carry
    
13.             
    
14.             # 严格模式：将计算出的单数字符（0-9）转回字符串形式
    
15.             digit = total % 10
    
16.             ans.append(chr(digit + ord('0')))
    
17.             
    
18.             carry = total // 10
    
19.             
    
20.             ind1 -= 1
    
21.             ind2 -= 1
    
22.         
    
23.         return "".join(ans[::-1])

复制代码

359. Logger Rate Limiter

简单题，但是这道题目可以 follow up。

AI 的 follow up 还是挺好的，学习了。

code

1. class Logger:
   
2. 
   
3.     def __init__(self):
   
4.         self.logger = dict()
   
5. 
   
6.     def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
   
7.         if message not in self.logger:
   
8.             self.logger[message] = timestamp + 10
   
9.             return True
   
10.         else:
    
11.             if timestamp >= self.logger[message]:
    
12.                 self.logger[message] = timestamp + 10
    
13.                 return True
    
14.             else:
    
15.                 return False
    
16. 
    
17. 
    
18. 
    
19. # Your Logger object will be instantiated and called as such:
    
20. # obj = Logger()
    
21. # param_1 = obj.shouldPrintMessage(timestamp,message)

复制代码

改进

其实我不是特别喜欢合并这个写法，因为这样虽然代码短了，但是两个判断合并了，其实并不清晰。

我们可以把“第一次遇到这个单词”和“遇到了但已经过了10秒冷却期”这两种可以打印的情况合并。

如果 message 不在字典里，或者当前时间 timestamp >= 字典里记录的时间，说明可以打印。

否则，说明还在冷却期内，不能打印。

1. class Logger:
   
2. 
   
3.     def __init__(self):
   
4.         # 记录每个 message 下一次允许打印的时间戳
   
5.         self.msg_earliest_time = {}
   
6. 
   
7.     def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
   
8.         # 如果当前时间还没到允许打印的时间，直接拒绝
   
9.         if message in self.msg_earliest_time and timestamp < self.msg_earliest_time[message]:
   
10.             return False
    
11.             
    
12.         # 否则（不在字典里，或者已经过了冷却期），更新时间并允许打印
    
13.         self.msg_earliest_time[message] = timestamp + 10
    
14.         return True

复制代码

如果面试官看你秒杀了这道题，通常会抛出下面这个 Follow-up（追问）：面试官： “如果这个 Logger 运行了很久，有海量的不同 message 进来，你的 Dict 会越来越大，导致内存撑爆（OOM）。由于题目说了 timestamp 是递增进来的，你该怎么优化内存？”💡 破题思路：既然 timestamp 是单调递增的，那些已经过了很久的日志（比如几小时前的），我们其实不需要一直存在字典里。解法： 我们可以配合使用一个 双端队列（collections.deque） 来按时间顺序存储 (timestamp, message)。每次调用 shouldPrintMessage 时，先看队列头部，把那些 timestamp <= 当前时间 - 10 的过期垃圾数据从队列和字典中彻底删除（Clean up）。这样字典里就永远只保留最近 10 秒的数据，内存直接降为 $O(1)$ 常数级别！

简单来说：deque 负责帮你找出“谁过期了”，然后你根据 deque 提供的信息，手动去把 dict 里对应的记录删掉。


我们可以把原本存时间戳的 dict，简化成一个 set（哈希集合），专门用来存放“当前处于 10 秒冷却期内的日志”。

💡 清理机制是怎么运作的？

deque 维护时间顺序：队列里只存 允许打印 的日志，格式为 (timestamp, message)。因为题目保证了时间戳是递增进来的，所以队头（左侧）永远是最老的数据。

set 维护 $O(1)$ 查询：集合里存放当前还在队列里的 message。联动清理（核心所在）：每次来一条新日志，在判断它能不能打印之前，先去检查 deque 的队头。如果队头日志的时间已经 $\ge 10$ 秒了，就把它从 deque 里 popleft() 弹出来，同时！拿弹出来的那个 message 去把 set 里的记录 remove 掉。

1. from collections import deque
   
2. 
   
3. class Logger:
   
4.     def __init__(self):
   
5.         # set 用来做 O(1) 的快速查找，记录“当前处于冷却期的 message”
   
6.         self.msg_set = set()
   
7.         # deque 用来记录打印历史，格式: (timestamp, message)
   
8.         self.msg_queue = deque()
   
9. 
   
10.     def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
    
11.         # 1. 核心清理逻辑：从队头检查，把 10 秒前的“老古董”全部扔掉
    
12.         while self.msg_queue and timestamp - self.msg_queue[0][0] >= 10:
    
13.             old_timestamp, old_message = self.msg_queue.popleft()
    
14.             # ★ 就在这一步！利用从 deque 拿到的 old_message，去清理 set（相当于清理 dict）
    
15.             self.msg_set.remove(old_message)
    
16.             
    
17.         # 2. 判断当前 message 是否还在 set 里（是否还在冷却期）
    
18.         if message in self.msg_set:
    
19.             return False
    
20.             
    
21.         # 3. 如果允许打印，加入队列和集合，开始它自己的 10 秒冷却期
    
22.         self.msg_set.add(message)
    
23.         self.msg_queue.append((timestamp, message))
    
24.         return True

复制代码

346. Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

MovingAverage(int size) Initializes the object with the size of the window size.
double next(int val) Returns the moving average of the last size values of the stream.


Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3


Constraints:

1 <= size <= 1000
-105 <= val <= 105
At most 104 calls will be made to next.


这道题目还是挺简单的，我一开始想的是中位数，做到一半发现是 avg 那就简单了。

Using Dequeue

1. class MovingAverage:
   
2. 
   
3.     def __init__(self, size: int):
   
4.         self.size = size
   
5.         self.nums = deque([])
   
6.         self.sumALL = 0
   
7. 
   
8.     def next(self, val: int) -> float:
   
9.         self.sumALL += val
   
10.         self.nums.append(val)
    
11. 
    
12.         if len(self.nums) > self.size:
    
13.             removed_val = self.nums.popleft()
    
14.             self.sumALL -= removed_val
    
15. 
    
16. 
    
17.         return self.sumALL / len(self.nums)
    
18. 
    
19. 
    
20. # Your MovingAverage object will be instantiated and called as such:
    
21. # obj = MovingAverage(size)
    
22. # param_1 = obj.next(val)

复制代码

优化，不是用 Dequeue， 使用数组。

用一个大小固定的列表 + 指针取模来模拟 Dequeue

1. class MovingAverage:
   
2.     def __init__(self, size: int):
   
3.         self.size = size
   
4.         self.queue = [0] * size  # 初始化一个固定大小的数组
   
5.         self.window_sum = 0
   
6.         self.count = 0           # 记录总共接收到的数字个数
   
7. 
   
8.     def next(self, val: int) -> float:
   
9.         self.count += 1
   
10.         
    
11.         # 计算当前要插入或覆盖的索引位置 (通过取模实现环形)
    
12.         tail = (self.count - 1) % self.size
    
13.         
    
14.         # 减去旧值，加上新值
    
15.         self.window_sum = self.window_sum - self.queue[tail] + val
    
16.         
    
17.         # 更新数组
    
18.         self.queue[tail] = val
    
19.         
    
20.         # 计算分母：在没填满之前除以 count，填满后除以 size
    
21.         return self.window_sum / min(self.size, self.count)

复制代码

补充内容 (2026-06-12 10:30 +08:00):
min(self.count, self.size)

是很高明的技巧，这样省去了判断是不是数组填满的问题。

LC. 836. Rectangle Overlap

这个就是很经典的 AABB 碰撞检测（Axis-Aligned Bounding Box）在 Object detection 中也是常用的，不过我完全忘了。

也不是完全忘了，我知道不能去列举 BBox 到底是怎么排列的，但是还是没想出来最优的解法。

囧！

思路 1: 反向思维（排除法）—— 推荐！思路： 证明两个矩形“重叠”很难，但证明它们“不重叠”非常简单！两个矩形在什么情况下绝对碰不到？只有四种情况：rec1 在 rec2 的左侧完全错开：rec1 的右边缘 $\le$ rec2 的左边缘 (rec1[2] <= rec2[0])rec1 在 rec2 的右侧完全错开：rec1 的左边缘 $\ge$ rec2 的右边缘 (rec1[0] >= rec2[2])rec1 在 rec2 的下方完全错开：rec1 的上边缘 $\le$ rec2 的下边缘 (rec1[3] <= rec2[1])rec1 在 rec2 的上方完全错开：rec1 的下边缘 $\ge$ rec2 的上边缘 (rec1[1] >= rec2[3])只要这四种情况有一种发生，就不重叠。反之，就必定重叠。

1. class Solution:
   
2.     def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
   
3.         # rec1: [x1, y1, x2, y2]
   
4.         # rec2: [x3, y3, x4, y4]
   
5.         
   
6.         # 判断四个"不重叠"的条件
   
7.         # 注意: 题目说 touching (贴边) 不算重叠，所以用 <= 或 >=
   
8.         is_left   = rec1[2] <= rec2[0] # rec1 完全在 rec2 左边
   
9.         is_right  = rec1[0] >= rec2[2] # rec1 完全在 rec2 右边
   
10.         is_bottom = rec1[3] <= rec2[1] # rec1 完全在 rec2 下边
    
11.         is_top    = rec1[1] >= rec2[3] # rec1 完全在 rec2 上边
    
12.         
    
13.         # 如果以上任意一个成立，就不重叠；全部不成立，才重叠。
    
14.         return not (is_left or is_right or is_bottom or is_top)

复制代码

思路 2: 正向思维（投影法 / 降维打击）思路： 两个 2D 矩形如果重叠，意味着它们在 X 轴上的投影是重叠的，并且在 Y 轴上的投影也是重叠的。这样就把复杂的 2D 问题变成了两个简单的 1D 线段交集问题。对于 X 轴线段 $[x_{1}, x_{2}]$ 和 $[x_{3}, x_{4}]$，重叠的条件是：左端点的最大值 < 右端点的最小值。Y 轴同理。

1. class Solution:
   
2.     def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
   
3.         # X 轴投影有重叠: max(左端点) < min(右端点)
   
4.         x_overlap = max(rec1[0], rec2[0]) < min(rec1[2], rec2[2])
   
5.         
   
6.         # Y 轴投影有重叠: max(下端点) < min(上端点)
   
7.         y_overlap = max(rec1[1], rec2[1]) < min(rec1[3], rec2[3])
   
8.         
   
9.         # 必须 X 轴和 Y 轴都有重叠，矩形才会重叠
   
10.         return x_overlap and y_overlap

复制代码

就这道题而言，解法 1 更加简单直接，但是从更加广泛应用的角度，其实 2 更好。

因为它可以直接用到 223. Rectangle Area 上。


Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).



Example 1:

Rectangle Area
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16


Constraints:

-104 <= ax1 <= ax2 <= 104
-104 <= ay1 <= ay2 <= 104
-104 <= bx1 <= bx2 <= 104
-104 <= by1 <= by2 <= 104

223. Rectangle Area
Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.

The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).

The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).



Example 1:

Rectangle Area
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
Example 2:

Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16


Constraints:

-104 <= ax1 <= ax2 <= 104
-104 <= ay1 <= ay2 <= 104
-104 <= bx1 <= bx2 <= 104
-104 <= by1 <= by2 <= 104

核心原则：永远不要让负数的宽和高参与乘法运算。 要解决这个问题，不要在最后乘出来再去判断，而是要在计算宽和高的阶段，就把负数“掐死”在摇篮里。技巧：套一个 max(0, 值)。

1. class Solution:
   
2.     def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
   
3.         # 1. 计算重叠的宽和高
   
4.         # 技巧：用 max(0, ...) 兜底。如果没重叠算出来是负数，直接强制归零
   
5.         """
   
6.         核心原则：永远不要让负数的宽和高参与乘法运算。 要解决这个问题，不要在最后乘出来再去判断，而是要在计算宽和高的阶段，就把负数“掐死”在摇篮里。技巧：套一个 max(0, 值)。
   
7.         """
   
8.         overlap_width = max(0, min(ax2, bx2) - max(ax1, bx1))
   
9.         overlap_height = max(0, min(ay2, by2) - max(ay1, by1))
   
10.         
    
11.         # 2. 计算重叠面积
    
12.         # 此时 overlap_width 和 overlap_height 最少也是 0，绝对不会出现"负负得正"
    
13.         interArea = overlap_width * overlap_height
    
14.         
    
15.         # 3. 计算各自的独立面积
    
16.         totalArea = (ay2 - ay1) * (ax2 - ax1) + (by2 - by1) * (bx2 - bx1)
    
17. 
    
18.         # 4. 直接返回结果，无需 if-else
    
19.         # 因为如果没有重叠，interArea 自然就是 0，减去 0 没有任何影响
    
20.         return totalArea - interArea

复制代码

LC. 3612. Process String with Special Operations I
Hint
You are given a string s consisting of lowercase English letters and the special characters: *, #, and %.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.
Return the final string result after processing all characters in s.



Example 1:

Input: s = "a#b%*"

Output: "ba"

Explanation:

i        s[i]        Operation        Current result
0        'a'        Append 'a'        "a"
1        '#'        Duplicate result        "aa"
2        'b'        Append 'b'        "aab"
3        '%'        Reverse result        "baa"
4        '*'        Remove the last character        "ba"
Thus, the final result is "ba".

Example 2:

Input: s = "z*#"

Output: ""

Explanation:

i        s[i]        Operation        Current result
0        'z'        Append 'z'        "z"
1        '*'        Remove the last character        ""
2        '#'        Duplicate the string        ""
Thus, the final result is "".



Constraints:

1 <= s.length <= 20
s consists of only lowercase English letters and special characters *, #, and %.

其实我觉得是简单题，当然它还有 II 那个就是 hard 了。

因为数据量翻倍才是考察能力的时候，需要上技巧。

这个数据量可以直接 simulation，因为撑满了，2^19 次方个字符，每次都翻倍。

1. class Solution:
   
2.     def processStr(self, s: str) -> str:
   
3.         res = []
   
4. 
   
5.         for ch in s:
   
6.             if ch == '*':
   
7.                 if res: res.pop()
   
8.             elif ch == '#':
   
9.                 if res: res += res
   
10.             elif ch == '%':
    
11.                 if res: res.reverse()
    
12.             else:
    
13.                 res.append(ch)
    
14.         
    
15.         return "".join(res)

复制代码

LC. 3614. Process String with Special Operations II

Hint
You are given a string s consisting of lowercase English letters and the special characters: '*', '#', and '%'.

You are also given an integer k.

Build a new string result by processing s according to the following rules from left to right:

If the letter is a lowercase English letter append it to result.
A '*' removes the last character from result, if it exists.
A '#' duplicates the current result and appends it to itself.
A '%' reverses the current result.
Return the kth character of the final string result. If k is out of the bounds of result, return '.'.



Example 1:

Input: s = "a#b%*", k = 1

Output: "a"

Explanation:

i        s[i]        Operation        Current result
0        'a'        Append 'a'        "a"
1        '#'        Duplicate result        "aa"
2        'b'        Append 'b'        "aab"
3        '%'        Reverse result        "baa"
4        '*'        Remove the last character        "ba"
The final result is "ba". The character at index k = 1 is 'a'.

Example 2:

Input: s = "cd%#*#", k = 3

Output: "d"

Explanation:

i        s[i]        Operation        Current result
0        'c'        Append 'c'        "c"
1        'd'        Append 'd'        "cd"
2        '%'        Reverse result        "dc"
3        '#'        Duplicate result        "dcdc"
4        '*'        Remove the last character        "dcd"
5        '#'        Duplicate result        "dcddcd"
The final result is "dcddcd". The character at index k = 3 is 'd'.

Example 3:

Input: s = "z*#", k = 0

Output: "."

Explanation:

i        s[i]        Operation        Current result
0        'z'        Append 'z'        "z"
1        '*'        Remove the last character        ""
2        '#'        Duplicate the string        ""
The final result is "". Since index k = 0 is out of bounds, the output is '.'.



Constraints:

1 <= s.length <= 105
s consists of only lowercase English letters and special characters '*', '#', and '%'.
0 <= k <= 1015
The length of result after processing s will not exceed 1015.

I 中，因为数据量极小，我们直接操作数组就搞定了。但在这道 II 里，s 的长度到了 10^5，而 k 和最终长度更是高达 10^15。这意味着：任何试图真正在内存里拼接字符串的解法，都会直接 OOM（内存超限）或 TLE（超时）。

LC. 1344. Angle Between Hands of a Clock

直接模拟，注意时针并不是在12个时的整点位置上。

1. class Solution:
   
2.     def angleClock(self, hour: int, minutes: int) -> float:
   
3.         # hour to angle
   
4.         hour_angle = hour * 30.0 + minutes * 0.5
   
5.         # minutes to angle
   
6.         minutes_angle = minutes * 6.0
   
7. 
   
8.         inner_angle = min( abs(hour_angle - minutes_angle), 360 - abs(hour_angle - minutes_angle))
   
9. 
   
10.         return inner_angle
    
11.         

复制代码

优化，就是 hour 可以取值 到 12， 所以会出现超出物理意义的答案但是不影响答案，因为是求差。

为了让数据在物理意义上更严谨（即指针角度永远保持在 [0, 360) 之间），我们可以对 hour 做一次 % 12 的取模操作。把 12 点映射为 0 点，这样计算出的角度永远不会超过 360 度。

LC. 1732. Find the Highest Altitude

1. class Solution:
   
2.     def largestAltitude(self, gain: List[int]) -> int:
   
3.         ans = 0
   
4.         curr_h = 0
   
5. 
   
6.         for g in gain:
   
7.             curr_h += g
   
8.             ans = max(curr_h, ans)
   
9.         
   
10.         return ans
    
11.         

复制代码

LC. 1833. Maximum Ice Cream Bars

发现这道题我当年刷过，不过其实是不对的思路。有了 AI 之后，辅助学习还是效率很高的。

我的思路，sort 然后贪心，尽可能买最便宜的。

1. class Solution:
   
2.     def maxIceCream(self, costs: List[int], coins: int) -> int:
   
3.         costs.sort()
   
4.         ans = 0
   
5.         for cost in costs:
   
6.             if coins >= cost:
   
7.                 coins -= cost
   
8.                 ans += 1
   
9.             else:
   
10.                 break # 买不起当前最便宜的了，后面的更贵，直接退出
    
11.         return ans

复制代码

但是这个题目其实有个条件

"You must solve the problem by counting sort." (你必须使用计数排序来解决此问题)

为什么要强制要求计数排序 (Counting Sort)？

我们看一眼数据范围（Constraints）：costs.length == n 且 n 最大是 100,000。costs[i] 的最大值也是 100,000。常规排序的时间复杂度是 $O(N \log N)$。但是，当数组中元素的最大值不大时，使用基于数组下标的“计数排序”，可以将时间复杂度降到惊人的 $O(N + M)$（$M$ 是雪糕的最大价格）。这就是这道题真正的考点。

解法思路

3. 核心思路：计数排序模型
既然知道每个雪糕的价格不超过 100,000，我们可以创建一个数组（或者 Python 的哈希表/Counter），把价格作为下标，把这个价格的雪糕数量作为值。

具体步骤：

找出雪糕里的最高价格（为了确定计数数组的大小）。

遍历 costs，统计每个价格的雪糕有多少根。

从价格 1 开始从小到大遍历：

如果当前价格的雪糕有货，并且我们手里的 coins 还够买，就尽可能多地买。

计算我们最多能买几根（受限于“存货量”和“我们手里的钱”）。

扣除相应的钱，增加购买数量。

如果钱不够买哪怕一根当前价格的雪糕了，说明后面的更买不起，直接结束。

1. class Solution:
   
2.     def maxIceCream(self, costs: List[int], coins: int) -> int:
   
3.         if not costs: return 0
   
4.         
   
5.         # 1. 找到最大价格，初始化计数数组
   
6.         max_cost = max(costs)
   
7.         # freq[i] 表示价格为 i 的雪糕数量
   
8.         freq = [0] * (max_cost + 1)
   
9.         
   
10.         # 2. 统计每个价格的雪糕数量
    
11.         for cost in costs:
    
12.             freq[cost] += 1
    
13.             
    
14.         ans = 0
    
15.         
    
16.         # 3. 从最便宜的雪糕（价格为 1）开始贪心购买
    
17.         for price in range(1, max_cost + 1):
    
18.             count = freq[price]
    
19.             
    
20.             if count == 0:
    
21.                 continue # 这个价格没有雪糕，看下一个价格
    
22.                
    
23.             if coins < price:
    
24.                 break # 连一根当前价格的雪糕都买不起了，直接结束
    
25.                
    
26.             # 计算当前价格下，我们最多能买几根
    
27.             # 要么把存货全买了 (count)，要么把钱花光能买多少买多少 (coins // price)
    
28.             buy = min(count, coins // price)
    
29.             
    
30.             # 更新已买数量和剩余的钱
    
31.             ans += buy
    
32.             coins -= buy * price
    
33.             
    
34.         return ans

复制代码

计数排序是用空间换时间的经典体现。对于这道题的数据规模（$N=10^5, M=10^5$），$O(N + M)$ 大约是 $2 \times 10^5$ 次操作，远远少于 $O(N \log N)$ 的大约 $1.6 \times 10^6$ 次操作，在运行速度上有质的飞跃。