剑指Offer-栈队列堆专题

9. 用两个栈实现队列

题目描述

用两个栈来实现一个队列，完成队列的push和pop操作

Input:
["push 1", "push 2", "pop", "pop"]

Output:
1, 2

题解

思路（双栈法）：
元素进栈后，只能优先弹出末尾元素，但是队列每次弹出的却是最先进去的元素，如果能够将栈中元素全部取出来，才能访问到最前面的元素，因此，使用另一个栈来辅助取出。

插入与删除的时间复杂度都是O(1)，空间复杂度O(n)

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        self.stack1.append(node)
    
    def pop(self):
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        res = self.stack2.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        
        return res

if __name__ == "__main__":
    queue = Solution()
    queue.push(1)
    queue.push(2)
    print(queue.pop())
    print(queue.pop())
        

1
2

30. 包含min函数的栈

题目描述

实现一个包含min()函数的栈，该方法返回当前栈中最小的值。此栈包含的方法有：

push(value)：将value压入栈中
pop()：弹出栈顶元素
top()：获取栈顶元素
min()：获取栈中最小元素

Input:
["push -1", "push 2", "min", "top", "pop", "push 1", "top", "min"]

Output:
-1, 2, 1, -1

题解

思路1（双栈法）：
初始化一个原始栈和最小值栈，最小栈存储每次跟原栈中元素比较后的最小元素。

时间复杂度O(1)，空间复杂度O(n)

class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, node):
        self.stack.append(node)
        if not self.min_stack:
            self.min_stack.append(node)
        else:
            if self.min_stack[-1] < node:
                self.min_stack.append(self.min_stack[-1])
            else:
                self.min_stack.append(node)
        
    def pop(self):
        self.stack.pop()
        self.min_stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def min(self):
        return self.min_stack[-1]
    

if __name__ == "__main__":
    stack = Solution()
    stack.push(-1)
    stack.push(2)
    print(stack.min())
    print(stack.top())
    stack.pop()
    stack.push(1)
    print(stack.top())
    print(stack.min())
        

-1
2
1
-1

思路2（元组）：
使用一个栈，栈中元素是元组，元组的第一个元素是数值，第二个元素是最小值。

时间复杂度O(1)，空间复杂度O(1)

class Solution:
    def __init__(self):
        self.stack = []
        
    def push(self, node):
        if not self.stack:
            self.stack.append((node, node))
        else:
            self.stack.append((node, min(node, self.stack[-1][1])))
    
    def pop(self):
        self.stack.pop()
    
    def top(self):
        return self.stack[-1][0]
    
    def min(self):
        return self.stack[-1][1]
    

if __name__ == "__main__":
    stack = Solution()
    stack.push(-1)
    stack.push(2)
    print(stack.min())
    print(stack.top())
    stack.pop()
    stack.push(1)
    print(stack.top())
    print(stack.min())

-1
2
1
-1

31. 栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为栈的弹出顺序，假设压入的所有数字均不相等。

Input:
[1, 2, 3, 4, 5], [4, 5, 3, 2, 1]

Output:
True

题解

思路1（辅助栈）：
使用一个辅助栈来模拟，对于入栈序列，只要栈为空，则序列依次入栈，如果遇到一个栈等于出栈序列的元素，则放弃入栈，先让该元素出来。如果按照这样的方式两个序列都访问完，则说明是可以匹配入栈出栈次序的。

时间复杂度O(n)，空间复杂度O(n)

class Solution:
    def is_pop_order(self, push_v, pop_v):
        stack = []
        j = 0
        n = len(push_v)
        for i in range(n):
            while j < n and (len(stack) == 0 or stack[-1] != pop_v[i]):
                stack.append(push_v[j])
                j += 1
            if stack[-1] == pop_v[i]:
                stack.pop()
            else:
                return False
        
        return True
                

if __name__ == "__main__":
    push_v = [1, 2, 3, 4, 5]
    pop_v = [4, 5, 3, 2, 1]
    print(Solution().is_pop_order(push_v, pop_v))

True

题解

思路2（原地栈）：
遍历push数组时，用下标n表示栈空间，用j表示出栈序列的下标，遍历每一个待入栈的元素，加入栈顶，当栈不为空时，栈顶等于当前出栈序列，就出栈，同时减少n，最后如果栈空间大小n为0时，代表全部出栈完成，否则不匹配。

时间复杂度O(n)，空间复杂度O(1)

class Solution:
    def is_pop_order(self, push_v, pop_v):
        n = 0
        j = 0
        for num in push_v:
            push_v[n] = num
            while n >= 0 and push_v[n] == pop_v[j]:
                j += 1
                n -= 1
            n += 1
        
        return True if n == 0 else False
                

if __name__ == "__main__":
    push_v = [1, 2, 3, 4, 5]
    pop_v = [4, 5, 3, 2, 1]
    print(Solution().is_pop_order(push_v, pop_v))

True

40. 最小的k个数

题目描述

给定一个长度为n的可能有重复值的数组，找出其中不去重的最小的k个数。

Input:
[4, 5, 1, 6, 2, 7, 3, 8], 4

Output:
[1, 2, 3, 4]

题解

思路1（堆排序）：
要找到最小的k个元素，只需要准备k个数字，之后每次遇到一个数字能够快速的与这k个数字中最大的值进行比较，每次将最大的值替换掉，那么最后剩余的就是k个最小的数字了。优先考虑大根堆，限制堆的大小为k，那么堆顶就是k个数字的最大值，如果需要替换，则将这个最大值拿出，加入新的元素就行。

时间复杂度O(nlogk), 空间复杂度O(k)

import heapq
class Solution:
    def get_least_numbers(self, nums, k):
        res = []
        if len(nums) >= k and k != 0:
            pq = []
            for i in range(k):
                heapq.heappush(pq, (-1 * nums[i]))
            for i in range(k, len(nums)):
                if (-1 * pq[0]) > nums[i]:
                    heapq.heapreplace(pq, (-1 * nums[i]))
            for i in range(k):
                res.append(-1 * pq[0])
                heapq.heappop(pq)
        
        return res
    

if __name__ == "__main__":
    nums = [4, 5, 1, 6, 2, 7, 3, 8]
    k = 4
    print(Solution().get_least_numbers(nums, k))
    

[4, 3, 2, 1]

思路2（sort排序法）：
对数组按照递增顺序进行排序，取前k个元素。

时间复杂度O(nlogn), 空间复杂度O(1)

class Solution:
    def get_least_numbers(self, nums, k):
        res = []
        if k == 0 or len(nums) == 0:
            return res
        else:
            return sorted(nums)[:k]


if __name__ == "__main__":
    nums = [4, 5, 1, 6, 2, 7, 3, 8]
    k = 4
    print(Solution().get_least_numbers(nums, k))

[1, 2, 3, 4]

41.1 数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

Input:
[5,2,3,4,1,6,7,0,8]

Output:
[5.00, 3.50, 3.00, 3.50, 3.00, 3.50, 4.00, 3.50, 4.00]

题解

思路1（插入排序）：
使用插入排序的思路，对每个输入的元素，遍历已经有序的数组，将其插入到属于它的位置。

插入的时间复杂度是O(n)，获取中位数的时间复杂度是O(1)，空间复杂度O(n)

class Solution:
    def __init__(self):
        self.val = []
    
    def insert(self, num):
        if len(self.val) == 0:
            self.val.append(num)
        else:
            i = 0
            while i < len(self.val):
                if num <= self.val[i]:
                    break
                i += 1
            self.val.insert(i, num)
    
    def get_median(self):
        n = len(self.val)
        if n % 2 == 1:
            return self.val[n // 2]
        else:
            return (self.val[n // 2] + self.val[n // 2 - 1]) / 2.0
        
        
if __name__ == "__main__":
    s = Solution()
    s.insert(5)
    print(s.get_median())
    s.insert(2)
    print(s.get_median())
    s.insert(3)
    print(s.get_median())
    s.insert(4)
    print(s.get_median())
    s.insert(1)
    print(s.get_median())
    s.insert(6)
    print(s.get_median())
    s.insert(7)
    print(s.get_median())
    s.insert(0)
    print(s.get_median())
    s.insert(8)
    print(s.get_median())

5
3.5
3
3.5
3
3.5
4
3.5
4

题解

思路2（插入排序）：
中位数是数组中间的数字或两个数字的均值，他是数组较小的一半元素中最大的一个，同时也是较大的一半元素中最小的一个，因此可以使用堆排序。约定奇数个元素时取大顶堆的顶部值，偶数个元素时取两堆顶的平均值。

插入的时间复杂度是O(logn)，获取中位数的时间复杂度是O(1)，空间复杂度O(n)

import heapq
class Solution:
    def __init__(self):
        self.max = []
        self.min = []
    
    def insert(self, num):
        heapq.heappush(self.min, (-1 * num))
        heapq.heappush(self.max, -1 * self.min[0])
        heapq.heappop(self.min)
        if len(self.min) < len(self.max):
            heapq.heappush(self.min, -1 * self.max[0])
            heapq.heappop(self.max)
    
    def get_median(self):
        if len(self.min) > len(self.max):
            return self.min[0] * -1.0
        else:
            return (-1 * self.min[0] + self.max[0]) / 2
        
        
if __name__ == "__main__":
    s = Solution()
    s.insert(5)
    print(s.get_median())
    s.insert(2)
    print(s.get_median())
    s.insert(3)
    print(s.get_median())
    s.insert(4)
    print(s.get_median())
    s.insert(1)
    print(s.get_median())
    s.insert(6)
    print(s.get_median())
    s.insert(7)
    print(s.get_median())
    s.insert(0)
    print(s.get_median())
    s.insert(8)
    print(s.get_median())

5.0
3.5
3.0
3.5
3.0
3.5
4.0
3.5
4.0

41.2 字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。

Input:
"google"

Output:
"ggg#ll"

题解

思路（哈希表）：
使用哈希表统计字符出现的次数，在insert函数中对输入的字符，加到字符串最后，然后统计出现次数。在first_appearing_once函数中遍历该字符串，对于每个字符查找哈希表，返回第一个计数为1的字符，如果遍历完字符串后都没，则返回#。

插入的时间复杂度是O(1)，查询的时间复杂度是O(n)，空间复杂度O(n)

class Solution:
    def __init__(self):
        self.strs = ""
        self.hash_map = dict()
    
    def insert(self, char):
        self.strs += char
        if char in self.hash_map:
            self.hash_map[char] += 1
        else:
            self.hash_map[char] = 1
            
    
    def first_appearing_once(self):
        for c in self.strs:
            if self.hash_map[c] == 1:
                return c
        
        return '#'
        
        
if __name__ == "__main__":
    s = Solution()
    s.insert("g")
    print(s.first_appearing_once())
    s.insert("o")
    print(s.first_appearing_once())
    s.insert("o")
    print(s.first_appearing_once())
    s.insert("g")
    print(s.first_appearing_once())
    s.insert("l")
    print(s.first_appearing_once())
    s.insert("e")
    print(s.first_appearing_once())

g
g
g
#
l
l

59. 滑动窗口的最大值

题目描述

给定一个长度为n的数组num和滑动窗口的大小size，找出所有滑动窗口里数值的最大值。

Input:
[2, 3, 4, 2, 6, 2, 5, 1], 3

Output:
[4, 4, 6, 6, 6, 5]

题解

思路（暴力法）：
直接遍历数组，遍历起始位置为0，终止位置为n-size，求取该区间最大值即可

时间复杂度O(mn)，空间复杂度O(1)

class Solution:
    def max_in_windows(self, nums, size):
        n = len(nums)
        if n < size or size == 0:
            return []
        res = []
        for i in range(n - size + 1):
            res.append(max(nums[i: i + size]))
            
        return res

    
if __name__ == "__main__":
    nums = [2, 3, 4, 2, 6, 2, 5, 1]
    size = 3
    print(Solution().max_in_windows(nums, size))

[4, 4, 6, 6, 6, 5]

参考文章

本文是笔者通过下列网站学习的记录，有部分修改和补充，转载请注明出处，并附带下面链接。

1. 【CS-Notes剑指Offer题解】
2. 【牛客网剑指Offer】