Leetcode 【739、946、973】

题目描述：【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】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)