特殊数据结构

单调栈

模板

stack = []
right = [len(nums)] * len(nums)
left = [-1] * len(nums)
for i in range(len(nums)):
    while stack and nums[i] > nums[stack[-1]]:
        right[stack.pop()] = i
    left[i] = stack[-1] if stack else -1
    stack.append(i)  # 保存的是下一个最大的数对应的索引
print(right) # 右边比当前值大的第一个值的index
print(left) # 左边比当前值大的第一个值的index

每日温度[739]

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        res = [0]*len(temperatures)
        for i in range(len(temperatures)):
            while stack and temperatures[i]>temperatures[stack[-1]]:
                c = stack.pop()
                res[c] = i - c
            stack.append(i)
        return res

下一个更大元素 I[496]

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        d = {}
        for i in range(len(nums2)):
            while stack and nums2[i]>nums2[stack[-1]]:
                d[nums2[stack.pop()]] = nums2[i]
            stack.append(i) #保存的是下一个最大的数对应的索引
        res = []
        for i in nums1:
            if i in d:
                res.append(d[i])
            else:
                res.append(-1)
        return res

接雨水[42]

class Solution:
    def trap(self, height: List[int]) -> int:
        def get_max_weight(height):
            left = [0] * len(height) # 注意：这里初始化为0
            for i in range(1, len(height)):
                left[i] = max(left[i-1], height[i-1]) # 注意：这里从height[i-1]对比
            return left
        left_max = get_max_weight(height)
        right_max = get_max_weight(height[::-1])[::-1]
        print(height)
        print(left_max)
        print(right_max)
        res = 0
        for i in range(len(height)):
            res = res + max(0, min(left_max[i], right_max[i])-height[i])
        return res

感觉不用单调栈来做，直接正反把arr遍历后，得到左右最大值，然后最大值的最小，减去当前的高度，就是可以接雨水的量。

柱状图中最大的矩形[84]

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        right = [len(heights)] * len(heights)
        left = [-1] * len(heights)
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                right[stack.pop()] = i
            left[i] = stack[-1] if stack else -1
            stack.append(i)  # 保存的是下一个最大的数对应的索引
        max_area = 0
        for i in range(len(heights)):
            max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))
        return max_area

盛水最多的容器 [11]

位于 https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150
思路:采用总结里面的第2点，涉及到while i<j

题号:11

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        area = 0
        while left <= right:
            temp = min(height[left], height[right]) * (right - left)
            if height[left] < height[right]:
                left = left + 1
            else:
                right = right - 1
            if temp > area:
                area = temp
        return area

单调队列

滑动数组最大值[239]

题目见 https://leetcode-cn.com/problems/sliding-window-maximum/ 题解有很多，如下：

# 单调队列
q, ret = deque(), []
for i, j in enumerate(nums):
    while q and nums[q[-1]] < j:
        q.pop()
    if q and q[0] <= i - k:
        q.popleft()
    q.append(i)
    if i >= k - 1:
        ret.append(nums[q[0]])
return ret

最小堆解法如下：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        import heapq
        q = []
        res = []
        for i in range(len(nums)):
            if len(q) <= k - 1:
                heapq.heappush(q, (-nums[i], i))
            else:
                res.append(-q[0][0])
                while q and i - q[0][1] >= k:
                    heapq.heappop(q)
                heapq.heappush(q, (-nums[i], i))
        res.append(-q[0][0])
        return res

题解 https://leetcode-cn.com/problems/sliding-window-maximum/solution/239hua-dong-chuang-kou-zui-da-zhi-bao-li-z4q2/

最小堆

模板

建议查看这里 https://blog.csdn.net/aabbccas/article/details/127742912 了解基础的使用，主要包括的函数和功能点

前 K 个高频元素[347]

解法如下：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import defaultdict
        import heapq
        d = defaultdict(int)
        for i in nums:
            d[i] = d[i] + 1
        cnt_key_value = []
        for key, value in d.items():
            cnt_key_value.append([value, key])
        temp = []
        for i in cnt_key_value:
            if len(temp) < k:
                heapq.heappush(temp, i)
            else:
                if i[0] > temp[0][0]:
                    heapq.heappop(temp)
                    heapq.heappush(temp, i)
        return [i[1] for i in temp]

最大的K个就用最小堆，如果是最小的k个就要取负了

数组中的第K个最大元素[215]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        temp = []
        for i in range(len(nums)):
            if len(temp)<k:
                heapq.heappush(temp, nums[i])
            else:
                if nums[i]>temp[0]:
                    heapq.heappop(temp)
                    heapq.heappush(temp, nums[i])
        return temp[0]

最大的K个就用最小堆，如果是最小的k个就要取负了

分割数组为连续子序列[659]

import heapq
from collections import defaultdict

class Solution:
    def isPossible(self, nums):
        chains = defaultdict(list)
        for i in nums:
            if not chains[i-1]:
                heapq.heappush(chains[i],1)
            else:
                min_len = heapq.heappop(chains[i-1])
                heapq.heappush(chains[i],min_len+1)
        for _,chain in chains.items():
            if chain and chain[0] < 3:
                return False
        return True

字典的键为序列结尾数值，值为结尾为该数值的所有序列长度（以堆存储）。
更新方式：每遍历一个数，将该数加入能加入的长度最短的序列中，不能加入序列则新建一个序列；然后更新字典。比如
当i=7时候，前面只有6能保持一个连续的序列，因此为2，这个2也是从6中来的，6这个键对应的值是[1,3]，然后pop之后给7加上去的。

最接近原点的 K 个点[973]

代码如下：

# 最小堆
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        import heapq
        points_distance = []
        for idc, i in enumerate(points):
            dis = i[0]*i[0] + i[1] * i[1]
            if len(points_distance)<k:
                heapq.heappush(points_distance, (-dis, idc))
            else:
                if dis > points_distance[0][0]:
                    heapq.heappop(points_distance)
                    heapq.heappush(points_distance, (-dis, idc))
        return [points[i[1]] for i in points_distance]
# NB一句话
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda x: (x[0] ** 2 + x[1] ** 2))
        return points[:k]