Algorithm
本周选择的算法题是：Sliding Window Maximum。
规则
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Example 5:
Input: nums = [4,-2], k = 2
Output: [4]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Solution
大顶堆：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = [(-nums[i], i) for i in range(k)]
heapq.heapify(q)
ans = [-q[0][0]]
for i in range(k, len(nums)):
heapq.heappush(q, (-nums[i], i))
while q[0][1] <= i - k:
heapq.heappop(q)
ans.append(-q[0][0])
return ans
单调栈：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
stack = []
for i in range(k):
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
stack.append(i)
ans = [nums[stack[0]]]
for i in range(k, len(nums)):
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
stack.append(i)
while stack[0] <= i - k:
stack.pop(0)
ans.append(nums[stack[0]])
return ans
Review
Go Does Not Need a Java Style GC
这篇文章从语言的实现层面解释了为什么 Go 不需要像 Java 那样的 GC。文章的几个关键点是：
- 为什么 Java 需要依赖 GC
- 内存碎片对 GC 有何影响
- 值类型又是如何影响 GC 的
- 为什么 Go 不需要分代 GC
- Go 是如何用逃逸分析降低 GC 压力的
- 为什么 Go 不需要压缩 GC
- Go 是如何并发使用 GC 的
全文看下来很畅快~!
Tip
Git 的 patch 指令可以使用交互式工具选择要提交的代码片段：
git add -p