題目描述：【Stack】739. Daily Temperatures
解題思路：
這道題是給一個(gè)溫度列表赤惊，重新生成一個(gè)列表：對(duì)應(yīng)位置是需要再等待多久溫度才會(huì)升高超過該日的天數(shù)。
看了下數(shù)據(jù)范圍勇哗，直接暴力肯定不行昼扛。再讀一下題目想到可以使用遞減棧（棧中存儲(chǔ)遞減的溫度）來解決。為了記錄每個(gè)溫度的位置，還要在棧中存儲(chǔ)對(duì)應(yīng)溫度的索引斯稳，即（索引海铆，溫度）。做法如下：
如果棧中有溫度挣惰，且當(dāng)前溫度比棧中溫度大卧斟，就出棧，當(dāng)前索引減去出棧溫度的索引就是對(duì)應(yīng)的結(jié)果憎茂。每次比較完后珍语，將當(dāng)前溫度入棧。
舉個(gè)例子：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，不執(zhí)行操作）-> [(2, 75), (3, 71), (4, 69)] （69 < 71馋评，不執(zhí)行操作）-> [(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，不執(zhí)行操作）蜕青，結(jié)束苟蹈。最后，棧中剩下的一定是個(gè)遞減序列市咆，全部為 0 即可汉操。可以得到結(jié)果 ans = [1, 1, 4, 2, 1, 1, 0, 0]。
Python3 實(shí)現(xiàn)：
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]: # 當(dāng)前數(shù)比棧頂數(shù)大蒙兰，出棧
ind, _ = stack.pop()
ans[ind] = i - ind
stack.append((i, T[i]))
return ans
題目描述：【Two Pointers】946. Validate Stack Sequences
解題思路：
這道題是給 pushed 和 popped 兩個(gè)序列磷瘤，判斷是否 pushed 序列能夠通過 pop 操作得到 popped 序列。
只需要使用兩個(gè)指針 i搜变、j 分別指向 pushed 和 popped采缚，如果 pushed[i] != popped[j]，i 往后移挠他，直到找到第一個(gè)能夠和 popped 序列對(duì)應(yīng)的 pop 位置扳抽。然后，pushed 刪除當(dāng)前元素 pushed[i]，同時(shí) i 向前移動(dòng)一位贸呢，代表出棧镰烧。j 向后移動(dòng)一位，判斷下一個(gè) pop 的位置楞陷。
注意到如果剛開始就相同怔鳖，如 pushed = [0, 1, 2]，popped = [0, 2, 1]固蛾，刪除 pushed[0] 后索引 i 會(huì)變成 -1结执，因此還要加一個(gè)判斷，就是如果 i < 0艾凯，讓 i = 0 即可献幔。
Python3 實(shí)現(xiàn)：
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起始位置對(duì)應(yīng)，del后i會(huì)變?yōu)?1
j += 1
# 滿足題意的一定是最后pushed為空且j到達(dá)了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
解題思路：
這道題是給一些坐標(biāo)蜡感，求距離原點(diǎn) (0, 0) 前 K 小距離（歐氏距離）的那些坐標(biāo)。
思路很直接：先求出所有點(diǎn)距離原點(diǎn)的距離（O(n) 的復(fù)雜度）恃泪，然后按照距離從小到大排序（O(nlogn) 的復(fù)雜度）铸敏，最后輸出前 K 個(gè)結(jié)果。總的時(shí)間復(fù)雜度為 O(nlogn)悟泵。
為了在排序距離時(shí)記錄原來坐標(biāo)的位置，可以以（距離闪水，索引）的形式一起排序糕非，輸出前 K 個(gè)結(jié)果時(shí)，就可以根據(jù)索引找到原來坐標(biāo)的位置球榆。實(shí)現(xiàn)代碼如代碼1所示：
Python3 實(shí)現(xiàn)：
代碼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
實(shí)際上，sorted 函數(shù)可以通過指定 key 來直接定義排序規(guī)則持钉，就不需要像代碼1那樣算距離的時(shí)候還要保存索引了衡招。實(shí)現(xiàn)代碼如代碼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 大）個(gè)元素可以使用最小優(yōu)先隊(duì)列（或最大優(yōu)先隊(duì)列）每强。我們知道始腾，優(yōu)先隊(duì)列不是真正的隊(duì)列，它只是維護(hù)的一個(gè)堆空执，優(yōu)先隊(duì)列每次輸出的是最大（或最欣思）的堆頂元素，而不是遵循先入先出辨绊。輸出元素的時(shí)間復(fù)雜度為 O(logn)奶栖。
可以使用 Python 中的 heapq 組件，通過調(diào)用 heapq.nsmallest(K, points, key = lambda x: x[0]**2 + x[1]**2) （取最大的 K 個(gè)元素對(duì)應(yīng)函數(shù)是 heapq.nlargest(...)）解決。
但是由于建堆的過程是 O(nlogn) 級(jí)別的宣鄙，因此總時(shí)間復(fù)雜度還是 O(nlogn)袍镀。實(shí)現(xiàn)代碼如代碼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)
