用 Python 解决数据结构与算法题 01

这是 Python 解决算法问题的第一期。我想以后每期写出三道题。本人是医学生,没有上过任何数据结构和算法课,对于解决算法题也纯属个人的课余兴趣爱好。还希望各位真正的大牛不吝赐教。我会继续坚持下去的。

设计一个有 getMin 功能的栈

题目:实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。 要求:

  1. poppushget_min 操作的时间复杂度都是 O(1)。
  2. 设计的栈类型可以使用线程的栈结构。

首先先使用 Python 实现一个简单的栈:

class Stack:
    __slots__ = ('__items')

    def __init__(self):
        self.__items = []

    def is_empty(self):
        return self.__items == []

    def peek(self):
        return self.__items[-1]

    def size(self):
        return len(self.__items)

    def push(self, new_value):
        self.__items.append(new_value)

    def pop(self):
        return self.__items.pop()

这个问题很简单,解决方法就是使用两个栈,一个用来存放数据,一个用来记录最小值即可。 在 push 新数据的时候,需要和存放最小值的栈 stack_min 栈顶的数据相比较。如果新数据比它小或者等于它,那么也把新数据 pushstack_min 的栈顶就可以了。 在 pop 的时候,需要检查输出的数据是否也存在在 stack_min 的栈顶,如果也存在的话,说明这个数据是栈内的最小值,也需要把它从 stack_minpop 出去。

class MyStack(object):

    def __init__(self):
        self.stack_data = Stack()
        self.stack_min = Stack()

    def push(self, new_value):
        self.stack_data.push(new_value)
        if self.stack_min.is_empty():
            self.stack_min.push(new_value)
        elif new_value <= self.get_min():
            self.stack_min.push(new_value)

    def pop(self):
        if self.stack_data.is_empty():
            raise Exception("Your stack is empty!")
        value = self.stack_data.pop()
        if value == self.get_min():
            self.stack_min.pop()
        return value

    def get_min(self):
        if self.stack_min.is_empty():
            raise Exception("Your stack is empty!")
        return self.stack_min.peek()

以下是用来测试的代码:

my_test_stack1 = MyStack()
my_test_stack1.push(3)
assert my_test_stack1.get_min() == 3

my_test_stack1.push(4)
assert my_test_stack1.get_min() == 3

my_test_stack1.push(5)
assert my_test_stack1.get_min() == 3

my_test_stack1.push(1)
assert my_test_stack1.get_min() == 1

my_test_stack1.push(2)
assert my_test_stack1.get_min() == 1

print(my_test_stack1.pop()) # 输出:2
assert my_test_stack1.get_min() == 1

print(my_test_stack1.pop()) # 输出:1
assert my_test_stack1.get_min() == 3

my_test_stack2 = MyStack()
my_test_stack2.pop() # 输出:Exception: Your stack is empty!

另一个稍稍不同的解决问题的方法是,当新 push 的数据比 stack_min 栈顶数据大时,再在 stack_min 的栈顶复制一个同样的栈顶值,这样就可以直接 pop 而不用检查这个值的大小了。这个方法会比上述方法在 push 时稍费空间,但在 pop 时稍省时间。但两种方法的空间和时间复杂度都是相同的。

仅用递归函数和栈操作逆序一个栈

题目:一个栈依次压入1,2,3,4,5,那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现栈中元素的逆序,但是只能用递归函数来实现,不能用其他数据结构。

逆序一个栈的步骤显而易见是先依次取出位于栈底的数据,然后再按照相反的顺序把数据压入即可了。而递归的思想在于,我先取出栈底的元素,然后把剩下的栈逆序,然后再把刚取出来的元素压进栈顶。同样,这道题的解答中使用的栈的实现与上面一题相同。

def get_last_element(stack):
    result = stack.pop()
    if stack.is_empty():
        return result
    else:
        last = get_last_element(stack)
        stack.push(result)
        return last

def reverse(stack):
    if stack.is_empty():
        return
    item = get_last_element(stack)
    reverse(stack)
    stack.push(item)

测试用的代码:

my_test_stack = Stack()
my_test_stack.push(1)
my_test_stack.push(2)
my_test_stack.push(3)
reverse(my_test_stack)
assert my_test_stack.pop() == 1, "现在栈顶应该是最先 push 进去的 1"
assert my_test_stack.pop() == 2
assert my_test_stack.pop() == 3

生成窗口最大值数据

题目:有一个整形数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。比如数组为[4, 3, 5, 4, 3, 3, 6, 7],就会有: [4 3 5] 4 3 3 6 7 4 [3 5 4] 3 3 6 7 4 3 [5 4 3] 3 6 7 4 3 5 [4 3 3] 6 7 4 3 5 4 [3 3 6] 7 4 3 5 4 3 [3 6 7] 最大值依次是[5, 5, 5, 4, 6, 7] 请实现一个函数,输入为数组 arr 和窗口大小 w,输出为各窗口的最大值数组。

看到题目,我想都没想就写好了第一个函数:

def get_max_in_window_v1(arr, w):
    if arr == [] or w < 1 or len(arr) < w:
        raise Exception("Wrong arr length or window size.")
    max_result = []
    for i in range(len(arr) - w + 1):
        max_result.append(max(arr[i:i+w]))
    return max_result

测试结果也正确,但是总觉得有些不好,仔细一看它的时间复杂度是 O(N * W) (因为循环里面的 max 函数的复杂度为 O(W) )。应该有更快的方法。于是想可以在每读取一个数组的时候,更新窗口最大值。你想节省时间,就必须得付出空间。于是乎使用另一个数组来存储最大值的下标,不断更新。

def get_max_in_window_v2(arr, w):
    if arr == [] or w < 1 or len(arr) < w:
        raise Exception("Wrong arr length or window size.")
    qmax = []
    max_result = []
    for index, item in enumerate(arr):
        while len(qmax) > 0 and arr[qmax[-1]] <= item:
            qmax.pop()
        qmax.append(index)
        if qmax[0] == index - w:
            qmax.pop(0)
        if index >= w-1:
            max_result.append(arr[qmax[0]])
    return max_result

主要就是在读取 arr 中的元素的时候,把最大值的下标存放在 qmax 的最左端。而小的依次往右排(你不能忽视那些相对小的数据,因为窗口在不停地向右移动。)这样,每读取一个元素,先更新 qmax,再把窗口最大值存放进 result,步骤非常清晰。在 Python 中 qmax.pop(0) 这条语句的时间复杂度是$O(W)$,是这个解法的一个缺憾。所以改天我想我需要写一个 Python 的链表实现,这样就比较好了。

测试通过:

print(get_max_in_window_v2(arr, 3)) # 输出:[5, 5, 5, 4, 6, 7]

感谢阅读。