用 Python 解决数据结构与算法题 01
这是 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]
感谢阅读。
