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

Oct 5, 2017

3 minute read

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

设计一个有 getMin 功能的栈

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

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

首先先使用 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 栈顶的数据相比较。如果新数据比它小或者等于它，那么也把新数据 push 进 stack_min 的栈顶就可以了。在 pop 的时候，需要检查输出的数据是否也存在在 stack_min 的栈顶，如果也存在的话，说明这个数据是栈内的最小值，也需要把它从 stack_min 中 pop 出去。

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]

感谢阅读。

xzy's blog

设计一个有 getMin 功能的栈

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

生成窗口最大值数据