Day 12 单调队列|优先队列大顶堆 (进阶): 239. 滑窗最大值，218. 天际线, 146. LRU 缓存, 380. Insert Delete GetRandom O(1), 71...

239. 滑动窗口最大值

思路
- example：[4,5,2,1,3], k = 3, output = [5,5,3]
- 暴力法：时间，空间
  - 遍历窗口右边界right, left = right-k+1, 当前窗口为 [left, right] (左闭右闭, 长度为k）
  - 本质上每次移动右边界，窗口更新：删除左边界元素，在右边加新元素
  - 如果用队列实现，可以用双端队列deque (左出右进）

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        for right in range(k-1, len(nums)):
            res.append(max(nums[right-k+1:right+1]))
        return res

1st 窗口：[4,5,2], max = 5
2nd 窗口：[5,2,1], max = 5
3rd窗口：[2,1,3], max = 3
维护size为k的窗口，比如deque，但是里面如果只是顺序存储元素的话，每个窗口只能线性找出最大值 $O(k)$ .
目标：deque里只存储必要的信息，使得能够在时间找到最大值。比如最大值在最左边（栈顶). 这说明deque里需要存储单调下降的元素。
- que = collections.deque()
- 第一步把4加进que, que = [4]
- 第二步：此时5 >= 4，说明前面的4不可能是所需要窗口的最大值（以数字4为左边界，或4包含在窗口内）。把4 pop出来： que.pop() (从右边pop) 。现在把5加进队列，que = [5].
- 第三步：此时2 < 5, 此数字有可能是后面窗口的最大值，所以加进队列，que = [5,2]. (第一个窗口形成，max = 5)
- 第四步：此时1 < 5, 加进队列，que = [5,2,1]. (第二个窗口：max = 5)
- 第五步：此时3 > 队列最右边的值1，当前包含3的窗口不可能会以1为最大值，所以pop出来：que.pop(); 然后3 >= 2，接着pop：que.pop(). que = [5,3]. 但是当把3加进窗口时，数字5已经不在考虑范围内，所以也要pop: que.popleft(). que = [3]. (第三个窗口：max = 3)
- 为方便，deque存储元素index，这样可以快速判断队列顶是否在窗口之外。

复杂度. 时间：O(n), 空间: O(n)

单调队列
- 单调下降队列
- 队列存储index
- 维护size k窗口
  - 用right计算左边界，和队列表头开始的index比较，弹出过期指标
  - 元素相同时，保存靠后的index

优先队列时间复杂度： $O(n \log(n))$

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        n = len(nums)
        que = collections.deque()
        right = 0
        while right < n:
            #size = len(que)
            #while size > 0 and nums[right] >= nums[que[size-1]]: # wrong, b/c size will change inside the loop
            while len(que) > 0 and nums[right] >= nums[que[len(que)-1]]: # >=:　数字相同时，保存靠后的数字（位置）
                que.pop()
            que.append(right)
            left = right - k + 1 # 窗口: [left, right], size  = k, 但是len(que)可能小于k
            if que[0] < left: 
                que.popleft()
            if left >= 0:
                res.append(nums[que[0]])
            right += 1
        return res

deque
单调下降队列
相同元素处理
index入队列
size，左边界控制

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        que = collections.deque() 
        res = []
        for i in range(n):
            while que and nums[i] >= nums[que[-1]]:
                que.pop()
            que.append(i)
            idx_start = que[0]
            if i - idx_start + 1 > k:
                que.popleft()
            if i >= k-1:
                res.append(nums[que[0]])
        return res

218. 天际线问题

思路
- example: buildings = [[2,9,10], [5,12,11], [10,12,9]], output = [[2,10], [5,11], [12,9], [13,0]]
- 扫描区间，暴力法, 搜索相交区间判断左端点或右端点是否转折点，时间 $O(n^2)$ 。
- 每个端点可分类：某区间左端点或某区间右端点。
  - 左端点：判断当前最大高度是否增加，是则说明此端点是上升转折点。（最大值的变化 $\Longrightarrow$ 优先队列（heapq, 最大堆或最小堆））
  - 右端点：“删除”对应区间左端点或高度影响，如果最大高度变小了，说明此端点是下降转斩点。
- 遍历端点：把端点加进列表，排序（by端点坐标，然后by高度（因为有可能某点同时是两个区间的端点）。为了区分左右端点，对左端点对应高度取负。[x, -h] 或 [x, h] 用正负高度区分左右端点。
  - 左端点
    - 把对应ｈ加进优先队列（最大堆）, 判断是否转折点。
  - 右端点
    - 在优先队列中删除对应-h (相当于把对应区间信息删除），重新heapify, 判断是否转折点。
- 端点列表：左右端点区分，排序（坐标，高度；左右端点相交时，左端点优先---间接的把可能等高度的两个区间拼接起来），依次遍历，左右端点不同处理方法
  - 左端点：当前负高度加入小顶堆，弹出当前最小负高度（最大正高度），判断当前左端点是否上升转折点（加入前后小顶堆首元素是否变化），是则加入结果列表（正高度）。（这一步假设大顶堆的最大负高度仍然“有效”。）
  - 右端点：对应的左端点失效，相应的把大顶堆中的-h移除，注意移除前后是否大顶堆首元素有变化，有则说明最大正高度有变化，该右端点是下降转折点，应加入结果列表。（这一步保证了当前小顶堆里的高度是有效的。）
- 小顶堆：存负高度（对正高度来说，是大顶堆）
复杂度. 时间： $O(n \log(n))$ 如果能在 $O(\log(n))$ 时间实现remove element in pq, 空间: $O(n)$
单调队列？

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        vertex_list = []
        for left, right, height in buildings: 
            vertex_list.append([left, -height]) # 处理某端点是两个区间的公共点。
            vertex_list.append([right, height])
        vertex_list.sort()
        res = []
        pq = [0] # initialize 0 height, max-heap, store negative height
        for vertex, height in vertex_list:
            if height < 0: # left endpt of an interval
                pre_max = pq[0]
                heapq.heappush(pq, height) # 永远加入 height < 0
                if pre_max != pq[0]:
                    res.append([vertex, -pq[0]]) # save positive height
            else: # right endpt of an interval, 这一步不需要把高度加进pq(遍历左端点的时候已加入）
                pre_max = pq[0]
                pq.remove(-height) # only remove one item
                heapq.heapify(pq)
                if pre_max != pq[0]:
                    res.append([vertex, -pq[0]])
        return res

优先队列改进版, pq保存[高度，右端点]信息，遍历端点（包括左右端点）。
- 小顶堆： [负高度，右端点]，加入右端点信息是为了方便判断当前大顶堆最大高度是否有效，若无效就弹出。（注意若当前高度不是目前最大高度，那么大顶堆不会变化，这里与第一版有区别。）

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        vertex_list = []
        for left, right, height in buildings:
            vertex_list.append([left, -height, right]) # 左端点, 最后一个表示右端点
            vertex_list.append([right, height, right]) # 右端点
        vertex_list.sort(key=lambda x:(x[0], x[1])) # 左右端点相交时，左端点优先
        que = [[0, -float('inf')]] # [高度（负），对应右端点坐标]
        res = []
        for vertex, height, end in vertex_list:
            if height < 0: # 左端点
                pre_max = que[0][0]
                heapq.heappush(que, [height, end])
                if pre_max != que[0][0]:
                    res.append([vertex, -que[0][0]]) 
            else: # 右端点
                pre_max = que[0][0]
                while que and vertex >= que[0][1]: # 当前最大高度在vertex之前就失效了
                    heapq.heappop(que)
                if not que: # 表明之后区间左端点都大于vertex, 重启que
                    que = [[0, vertex]]
                if pre_max != que[0][0]:
                    res.append([vertex, -que[0][0]])
        return res

146. LRU 缓存

思路
- example

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)

cache.put(1, 1);
// cache = [(1, 1)]

cache.put(2, 2);
// cache = [(2, 2), (1, 1)]

cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1

cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头

cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据

cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

哈希链表=hash+双向链表

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头部和伪尾部节点    
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希表定位，再移到头部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果 key 不存在，创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量，删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
    
    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

380. Insert Delete GetRandom O(1)

思路
- example

插入，删除，获取随机元素这三个操作的时间复杂度必须都是 O(1)。
hash (dict) + list
在list末尾插入，删除。
self.nums.pop(-1)
random.choice(self.nums)

class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.pos = {}
        
    def insert(self, val):
        if val not in self.pos:
            self.nums.append(val)
            self.pos[val] = len(self.nums) - 1
            return True
        return False

    def remove(self, val):
        if val in self.pos:
            idx, last = self.pos[val], self.nums[-1]
            self.nums[idx], self.pos[last] = last, idx
            self.nums.pop(-1)
            del self.pos[val]
            return True
        return False
            
    def getRandom(self):
        return random.choice(self.nums)

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()