本文共 6121 字，大约阅读时间需要 20 分钟。

优化后的内容

LeetCode 225: 用队列实现栈

问题描述

栈是先进后出的数据结构，而队列是先进先出的。我们需要使用队列来实现栈的常见操作：push、pop、top和empty。以下是具体的操作定义：

• push(x): 将元素x推入栈顶。
• pop(): 移除栈顶元素。
• top(): 获取栈顶元素。
• empty(): 检查栈是否为空。

解决思路

为了实现栈的功能，我们可以利用两个队列来模拟栈的行为。具体来说，我们可以将一个队列用作入栈栈，另一个队列用作出栈栈。通过适当的逻辑操作，可以模拟栈的先进后出特性。

解决代码

class MyStack:
    def __init__(self):
        self.q1 = collections.deque()
        self.q2 = collections.deque()
    
    def push(self, x):
        if self.q1.empty():
            self.q2.append(x)
        else:
            self.q1.append(x)
    
    def pop(self):
        if self.q1.empty():
            if not self.q2.empty():
                while len(self.q2) > 1:
                    self.q1.append(self.q2.popleft())
                return self.q2.popleft()
        else:
            while not self.q2.empty() or not self.q1.empty():
                if self.q1.empty():
                    self.q2.append(self.q1.popleft())
                else:
                    return self.q1.popleft()
    
    def top(self):
        if self.q1.empty():
            if self.q2.empty():
                return 0
            else:
                return self.q2[-1]
        else:
            return self.q1[-1]
    
    def empty(self):
        return self.q1.empty() and self.q2.empty()

解释

• push(x): 判断入栈队列q1是否为空。如果为空，则将x推入出栈队列q2中；否则，将x推入入栈队列q1中。
• pop(): 如果入栈队列q1为空，说明所有元素都已经被移到q2中，取出q2的最后一个元素。否则，取出q1的最后一个元素。
• top(): 返回栈顶元素。如果q1为空，返回q2的最后一个元素；否则，返回q1的最后一个元素。
• empty(): 检查q1和q2是否都为空。如果都为空，返回True，否则返回False。

通过这种方法，我们可以使用队列来实现栈的基本操作，保持了先进后出的特性。

---

LeetCode 232: 用栈实现队列

问题描述

队列是先进先出的数据结构，而栈是先进后出的。我们需要使用栈来实现队列的常见操作：push、pop、peek和empty。以下是具体的操作定义：

• push(x): 将元素x推入队列的尾部。
• pop(): 从队列首部移除元素。
• peek(): 返回队列首部的元素。
• empty(): 检查队列是否为空。

解决思路

为了实现队列的功能，我们可以利用两个栈来模拟队列的行为。具体来说，我们可以将一个栈用作出队栈，另一个栈用作入队栈。通过适当的逻辑操作，可以模拟队列的先进先出特性。

解决代码

class MyQueue:
    def __init__(self):
        self.in_stack = collections.deque()
        self.out_stack = collections.deque()
    
    def push(self, x):
        self.in_stack.append(x)
    
    def pop(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.popleft())
        return self.out_stack.popleft()
    
    def peek(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.popleft())
        return self.out_stack[0]
    
    def empty(self):
        return not self.in_stack and not self.out_stack

解释

• push(x): 将元素x推入入队栈in_stack中。
• pop(): 如果出队栈out_stack为空，取出入队栈in_stack中的所有元素，并将它们推入out_stack中，然后取出out_stack的第一个元素。
• peek(): 如果出队栈out_stack为空，取出入队栈in_stack中的所有元素，并将它们推入out_stack中，然后返回out_stack的第一个元素。
• empty(): 检查in_stack和out_stack是否都为空。如果都为空，返回True，否则返回False。

通过这种方法，我们可以使用栈来实现队列的基本操作，保持了先进先出的特性。

---

LeetCode 155: 最小栈

问题描述

我们需要设计一个支持push、pop、top和getMin操作的栈，且在常数时间内能够检索到栈中的最小元素。以下是具体的操作定义：

• push(x): 将元素x推入栈中。
• pop(): 删除栈顶的元素。
• top(): 获取栈顶元素。
• getMin(): 检索栈中的最小元素。

解决思路

为了实现这个栈，我们可以使用两个栈来存储元素。一个栈用于正常的栈操作，另一个栈用于存储当前栈中最小元素。每当push操作执行时，我们需要检查当前栈是否为空以及最小栈是否为空，以决定如何更新栈的状态。

解决代码

class MinStack:
    def __init__(self):
        self.normal = collections.deque()
        self.min = collections.deque()
    
    def push(self, x):
        self.normal.append(x)
        if not self.min:
            self.min.append(x)
        else:
            if x < self.min[-1]:
                self.min.append(x)
            else:
                self.min.append(self.min[-1])
    
    def pop(self):
        if self.normal:
            self.normal.pop()
            if self.min and self.min[-1] == self.normal.pop():
                self.min.pop()
    
    def top(self):
        return self.normal[-1] if self.normal else 0
    
    def getMin(self):
        return self.min[-1] if self.min else 0

解释

• push(x): 将元素x推入normal栈中。如果min栈为空，则将x推入min栈中；否则，检查x是否小于min栈的栈顶元素。如果是，将x推入min栈中；否则，将min栈的栈顶元素推入min栈中。
• pop(): 如果normal栈不为空，移除栈顶元素。同时，如果该元素等于min栈的栈顶元素，则移除min栈的栈顶元素。
• top(): 返回normal栈的栈顶元素，如果normal栈为空，则返回0。
• getMin(): 返回min栈的栈顶元素，如果min栈为空，则返回0。

通过这种方法，我们可以在常数时间内检索到栈中的最小元素，同时支持栈的基本操作。

---

LeetCode 215: 找出第k大的元素

问题描述

在未排序的数组中找到第k大的元素。请注意，我们需要找的是数组排序后的第k大的元素，而不是第k个不同的元素。

解决思路

我们可以使用一个小顶堆来实现这个算法。小顶堆有一个特性是，堆顶是最小的元素。我们可以通过以下步骤来实现：

遍历数组中的每个元素。

将元素加入小顶堆中。如果堆的大小小于k，则将元素压入堆中。

如果堆的大小等于k，则比较当前元素与堆顶元素。如果当前元素更大，则将堆顶元素弹出，并将当前元素压入堆中；否则，将当前元素压入堆中。

最后，堆的顶部就是第k大的元素。

解决代码

import heapq
class Solution:
    def findKthLargest(self, nums, k):
        heap = []
        for num in nums:
            if len(heap) < k:
                heapq.heappush(heap, num)
            else:
                if num > heap[0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, num)
        return heap[0]

解释

• findKthLargest(nums, k): 初始化一个空的小顶堆heap。
• 遍历数组nums：对于每个元素num，判断堆的大小是否小于k。如果是，将num推入堆中。
• 如果堆的大小等于k：比较num和堆顶元素。如果num更大，则弹出堆顶元素，并将num推入堆中；否则，将num推入堆中。
• 返回结果：堆的顶部即为第k大的元素。

通过这种方法，我们可以在O(n log n)的时间复杂度内找到数组中的第k大的元素。

---

LeetCode 295: 找中位数

问题描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数是中间两个数的平均值。我们需要设计一个数据结构，支持以下操作：

• addNum(int num): 添加一个整数到数据结构中。
• findMedian(): 返回当前所有元素的中位数。

解决思路

我们可以使用两个堆来实现这个数据结构：一个小顶堆和一个大顶堆。小顶堆用于存储较小的一半元素，大顶堆用于存储较大的一半元素。通过维护这两个堆的大小关系，可以实现中位数的计算。

具体步骤如下：

addNum(num): 如果大顶堆为空，将num推入大顶堆中；否则，比较num与大顶堆的栈顶元素。

维护堆的平衡：如果大顶堆的大小大于等于小顶堆的大小，将较大的元素推入小顶堆中，并调整大顶堆的大小。

findMedian(): 如果大顶堆的大小大于小顶堆的大小，返回大顶堆的栈顶元素；否则，返回小顶堆和大顶堆栈顶元素的平均值。

解决代码

import heapq
class MedianFinder:
    def __init__(self):
        self.small = []
        self.big = []
    
    def addNum(self, num):
        if not self.big:
            heapq.heappush(self.big, num)
        else:
            if num > self.big[0]:
                heapq.heappush(self.big, num)
            else:
                heapq.heappush(self.small, num)
                if len(self.small) > len(self.big):
                    val = self.small.pop()
                    heapq.heappush(self.big, val)
    
    def findMedian(self):
        if len(self.big) > len(self.small):
            return self.big[0]
        else:
            return (self.small[0] + self.big[0]) / 2.0

解释

• addNum(num): 如果大顶堆为空，将num推入大顶堆中；否则，比较num与大顶堆的栈顶元素。如果num大于栈顶元素，将num推入大顶堆中；否则，将num推入小顶堆中。
• 维护堆的平衡：如果小顶堆的大小大于大顶堆的大小，将小顶堆的栈顶元素推入大顶堆中。
• findMedian(): 如果大顶堆的大小大于小顶堆的大小，返回大顶堆的栈顶元素；否则，返回小顶堆和大顶堆栈顶元素的平均值。

通过这种方法，我们可以在O(log n)的时间复杂度内进行addNum和findMedian操作，实现中位数的计算。

转载地址：http://vyfq.baihongyu.com/