本篇文章根据labuladong的算法小抄汇总自己设计数据结构的常见算法，采用python3实现

文章目录

• LRU算法
• • LRU缓存机制，T146
• 单调栈结构
• • 单调栈模板
  • 下一个更大元素Ⅰ，T496
  • 每日温度，T739
  • [循环数组]，下一个更大元素Ⅱ，T503
• 单调队列
• • 滑动窗口最大值，T239
• 二叉堆实现优先级队列
• • 二叉堆
  • 优先级队列
  • 实现上浮swim和下沉sink
  • 实现delMax和insert
• 队列实现栈，T225
• 栈实现队列，T232

LRU算法

LRU(Least Recently Used)算法是一种缓存淘汰机制。计算机的缓存容量有限，如果缓存满了就要删除一些内容，那么删除哪些内容呢？LRU认为最近使用过的数据是有用的，很久没用的就是无用的，内存满了就优先删掉很久没用过的数据。

LRU缓存机制，T146

题目：设计并实现一个满足LRU缓存约束的数据结构。

要求：put和get时间复杂度为O(1)

解决：哈希链表

1. 用python自带的哈希+双向链表OrderedDict

class LRUCache(collections.OrderedDict):
    def __init__(self,capacity):
        super().__init__()
        self.capacity = capacity
    def get(self,key):
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]
    def put(self,key,value):
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)

2. 自己实现

#双向链表
class DLinkedNode:
    def __init__(self,key=0,value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
    
class LRUCache:
    #以正整数作为容量初始化LRU缓存
    def __init__(self,capacity):
        self.cache = dict()
        #伪头部节点；伪尾部节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = self.capacity
        self.size = 0
        
    #如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
    def get(self,key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value
        
    #如果key已经存在，则变更其value；如key不存在，则向缓存中插入key-value；如插入导致容量超限，则逐出最久未使用的关键字
    def put(self,key,value):
        if key not in self.cache:
            node = DLinkedNode(key,value)
            self.cache[key] = value
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            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

单调栈结构

栈：先进后出。

单调栈：每次新元素入栈后，栈内元素都保持有序（单调递增或单调递减）

单调栈只处理一种典型问题Next Greater Element。

单调栈模板

给你一个数组nums，返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存-1。

def nextGreaterElement(nums):
    n = len(nums)
    res = [0 for i in range(n)]
    s = []
    for i in range(n-1,-1,-1):
        while s and s[-1] <= nums[i]:
            s.pop()
        res[i] = -1 if not s else s[-1]
        s.append(nums[i])
    return res

下一个更大元素Ⅰ，T496

def nextGreaterElement(nums1,nums2):
    res = {}
    stack = []
    for num in reversed(nums2):
        while stack and num >= stack[-1]:
            stack.pop()
        res[num] = stack[-1] if stack else -1
        stack.append(num)
    return [res[num] for num in nums1]

每日温度，T739

数组T存放近几天的气温，返回等长数组，计算对于每一天，至少等多少天才能等到一个更暖和的气温，如果等不到填0

def dailyTemperatures(T):
    n = len(T)
    res = [0 for i in range(T)]
    s = []
    for i in range(n-1,-1,-1):
        while s and T[s[-1]] <= T[i]:
            s.pop()
        res[i] = 0 if not s else s[-1]-i
        s.append(i)
    return res

[循环数组]，下一个更大元素Ⅱ，T503

常用套路：将数组长度翻倍

def nextGreaterElements(nums):
    n = len(nums)
    res = [0 for i in range(n)]
    stack = []
    for i in range(2*n-1,-1,-1):
        while s and s[-1] <= nums[i % n]:
            s.pop()
        res[i % n] = s[-1] if s else -1
        s.append(nums[i%n])
    return res

单调队列

单调队列主要解决滑动窗口相关问题

滑动窗口最大值，T239

题目：给定数组nums和正整数k，有一个大小为k的窗口在nums上从左到右滑动，请你输出每次窗口中k个元素的最大值。

#实现单调队列数据结构
class MonotonicQueue:
    def __init__(self):
        self.q = LinkedList()
    def push(self,n):
        while q and q.getLast() < n:
            q.pollLast()
        q.addLast(n)
    def max_(self):
        rerurn q.getFirst()
    def pop(self,n):
        if n == q.getFirst:
            q.pollFirst()
    
def maxSlidingWindow(nums,k):
    window = MonotonicQueue()
    res = []
    for i in range(len(nums)):
        #先把前k-1个填满
        if i < k - 1:
            window.push(nums[i])
        else:
            window.push(nums[i])
            res.append(window.max_())
            window.pop(nums[i-k+1])
    return res

官方解答：

def maxSlidingWindow(nums,k):
    n = len(nums)
    q = collections.deque()
    for i in range(k):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
    res = [nums[q[0]]]
    for i in range(k,n):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
        while q[0] <= i - k:
            q.popleft()
        res.append(nums[q[0]])
    return res

二叉堆实现优先级队列

二叉堆

【储存在列表里的完全二叉树】二叉堆在逻辑上是完全二叉树，只不过存储在数组里。一般的链表二叉树，我们操作节点的指针，而在数组里，我们把数组索引作为指针。

二叉堆主要操作：sink（下沉）；swim（上浮）

二叉堆主要应用：堆排序；优先级队列

注意：第一个索引0空着不用

#数组第0位空着不用
#父节点索引
def parent(root):
    return root // 2
#左孩子索引
def left(root):
    return root * 2
#右孩子索引
def right(root):
    return root * 2 + 1

最大堆：每个节点都大于等于它的两个子节点

最小堆：每个节点都小于等于它的两个子节点

优先级队列

性质：插入或删除元素时，元素会自动排序。

底层原理：二叉堆的操作

主要API：insert插入一个元素，delMax删除最大元素（最小堆则为delMin删除最小元素）

实现上浮swim和下沉sink

对于最大堆来说，可能出现以下破坏其性质的情况：

（1）如果某个节点A比它的子节点小，那么A就不配做父节点，应该下沉

（2）如果某个节点A比它的父节点大，那么A就不应该做子节点，应该上浮

实现delMax和insert

insert：把要插入的元素添加到堆底的最后，然后让其上浮到正确位置

delMax：把堆顶元素A和堆底最后的元素B对调，然后删除A，最后让B下沉到正确位置

class MaxPQ:
    def __init__(self,N=0,pq=[]):
        self.N = N
        self.pq = pq
    def parent(self,i):
        return i // 2
    def left(self,i):
        return i * 2
    def right(self,i):
        return i * 2 + 1    
    #交换两个元素
    def exch(self,i,j):
        pq[i],pq[j] = pq[j],pq[i]
    #比较两个元素
    def less(self,i,j):
        return pq[i] < pq[j]
    #上浮    
	def swim(self,k):
    	while (k > 1) and MaxPQ.less(MaxPQ.parent(k),k):
            MaxPQ.exch(MaxPQ.parent(k),k)
            k = MaxPQ.parent(k)
    #下沉
    def sink(self,k):
        while MaxPQ.left(k) <= N:
            older = MaxPQ.left(k)
            if (MaxPQ.right(k) <= N) and (MaxPQ.less(older,MaxPQ.right(k))):
                older = maxPQ.right(k)
            if maxPQ.less(older,k):
                break
            maxPQ.exch(k,older)
            k = older
    #插入一个新元素
    def insert(self,e):
        N += 1
        pq[N] = e
        MaxPQ.swim(N)
    #删除堆顶元素
    def delMax(self):
        maxValue = pq[1]
        MaxPQ.exch(1,N)
        pq[N] = None
        N -= 1
        maxPQ.sink(1)
        return maxValue

队列实现栈，T225

队列：先进先出

栈：先进后出

class MyStack:
    def __init__(self):
        self.q = []
        self.topelem = 0
        
    def push(self,x):
        self.q.append(x)
        self.topelem = x
        
    def top(self):
        return self.topelem
        
    def pop(self):
        size = len(self.q)
        while size > 2
            self.q.append(self.q.pop(0))
            size -= 1
        self.topelem = self.q[0]
        self.q.append(self.q.pop(0))
        return self.q.pop(0)
        
    def empty(self):
        return not self.q

pop时间复杂度为O(N)，其它都为O(1)

栈实现队列，T232

class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    #将元素x推到队列末尾
    #顺序添加进s1
    def push(self,x):
    	self.s1.append(x)
    
    #返回队列开头的元素
    #当s2为空时，可以把s1所有元素取出添加进s2
    def peek(self):
    	if not self.s2:
            while self.s1:
                self.s2.push(self.s1.pop())
        return self.s2[-1]
        
    #从队列开头移除并返回元素
    def pop(self):
    	self.peek()
        return self.s2.pop()
        
    #队列是否为空
    def empty(self):
        return (not self.s1) and (not self.s2)

最坏时间复杂度为O(N)，但均摊时间复杂度为O(1)，因为对于一个元素，最多只可能被搬运一次。