题目描述：【Stack】739. Daily Temperatures
解题思路：
这道题是给一个温度列表，重新生成一个列表：对应位置是需要再等待多久温度才会升高超过该日的天数。
看了下数据范围，直接暴力肯定不行。再读一下题目想到可以使用递减栈（栈中存储递减的温度）来解决。为了记录每个温度的位置，还要在栈中存储对应温度的索引，即（索引，温度）。做法如下：
如果栈中有温度，且当前温度比栈中温度大，就出栈，当前索引减去出栈温度的索引就是对应的结果。每次比较完后，将当前温度入栈。
举个例子：T = [73, 74, 75, 71, 69, 72, 76, 73]，栈的变化是 [(0, 73)] -> [(1, 74)] （74 > 73，73 出栈，ans[0] = 1 - 0 = 1）-> [(2, 75)] （75 > 74，74 出栈，ans[1] = 2 - 1 = 1）-> [(2, 75), (3, 71)] （71 < 75，不执行操作）-> [(2, 75), (3, 71), (4, 69)] （69 < 71，不执行操作）-> [(2, 75), (5, 72)] （72 > 69 和 71，69 和 71 依次出栈，ans[4] = 5 - 4 = 1, ans[3] = 5 - 3 = 2）-> [(6, 76)]（76 > 72 和 75，72 和 75 依次出栈，ans[5] = 6 - 5 = 1, ans[2] = 6 - 2 = 4）-> [(6, 76), (7, 73)]（73 < 76，不执行操作），结束。最后，栈中剩下的一定是个递减序列，全部为 0 即可。可以得到结果 ans = [1, 1, 4, 2, 1, 1, 0, 0]。
Python3 实现：
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = []
ans = [0] * len(T)
for i in range(len(T)):
while len(stack) > 0 and T[i] > stack[-1][1]: # 当前数比栈顶数大，出栈
ind, _ = stack.pop()
ans[ind] = i - ind
stack.append((i, T[i]))
return ans
题目描述：【Two Pointers】946. Validate Stack Sequences
解题思路：
这道题是给 pushed 和 popped 两个序列，判断是否 pushed 序列能够通过 pop 操作得到 popped 序列。
只需要使用两个指针 i、j 分别指向 pushed 和 popped，如果 pushed[i] != popped[j]，i 往后移，直到找到第一个能够和 popped 序列对应的 pop 位置。然后，pushed 删除当前元素 pushed[i]，同时 i 向前移动一位，代表出栈。j 向后移动一位，判断下一个 pop 的位置。
注意到如果刚开始就相同，如 pushed = [0, 1, 2]，popped = [0, 2, 1]，删除 pushed[0] 后索引 i 会变成 -1，因此还要加一个判断，就是如果 i < 0，让 i = 0 即可。
Python3 实现：
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
i = j = 0
while i < len(pushed) and j < len(popped):
if pushed[i] != popped[j]:
i += 1
else:
del pushed[i]
i -= 1
if i < 0: i = 0 # pushed和popped起始位置对应，del后i会变为-1
j += 1
# 满足题意的一定是最后pushed为空且j到达了popped的末尾
return True if len(pushed) == 0 and j == len(popped) else False
print(Solution().validateStackSequences([0,1,2], [0,2,1])) # True
题目描述：【Sort、Heap】973. K Closest Points to Origin
解题思路：
这道题是给一些坐标，求距离原点 (0, 0) 前 K 小距离（欧氏距离）的那些坐标。
思路很直接：先求出所有点距离原点的距离（O(n) 的复杂度），然后按照距离从小到大排序（O(nlogn) 的复杂度），最后输出前 K 个结果。总的时间复杂度为 O(nlogn)。
为了在排序距离时记录原来坐标的位置，可以以（距离，索引）的形式一起排序，输出前 K 个结果时，就可以根据索引找到原来坐标的位置。实现代码如代码1所示：
Python3 实现：
代码1：
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
dis = []
ans = []
for i, point in enumerate(points):
dis.append((point[0]*point[0]+point[1]*point[1], i)) # (距离，索引)
dis.sort()
for i in range(K):
ans.append(points[dis[i][1]])
return ans
实际上，sorted 函数可以通过指定 key 来直接定义排序规则，就不需要像代码1那样算距离的时候还要保存索引了。实现代码如代码2所示：
代码2：
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
return sorted(points, key = lambda x: x[0]**2 + x[1]**2)[:K]
取前 K 小（或 K 大）个元素可以使用最小优先队列（或最大优先队列）。我们知道，优先队列不是真正的队列，它只是维护的一个堆，优先队列每次输出的是最大（或最小）的堆顶元素，而不是遵循先入先出。输出元素的时间复杂度为 O(logn)。
可以使用 Python 中的 heapq 组件，通过调用 heapq.nsmallest(K, points, key = lambda x: x[0]**2 + x[1]**2) （取最大的 K 个元素对应函数是 heapq.nlargest(...)）解决。
但是由于建堆的过程是 O(nlogn) 级别的，因此总时间复杂度还是 O(nlogn)。实现代码如代码3所示：
代码3：
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
return heapq.nsmallest(K, points, key = lambda x: x[0]**2 + x[1]**2)
网友评论