栈与队列

发表于 | 分类于 ，

前几次在复盘笔试的时候，有遇到几题出现在面试指南中的原题，或者是基于面试指南修改的题目（就是改成带有自己公司色彩的题目），所以意识到这本书应该也得刷一刷，所以最近会更新刷书过程中遇到的之前没遇到过的题目的总结和思考。

栈与队列

栈和队列对于python来说是差不多的数据结构，因为他们都可以用python中的list来实现，只不过在出栈、出队列中略有差别。出栈是pop()，出队列是pop(0)。因为栈是先进后出的，而队列是先进后出的。在众多的相关类型的题目中，有一类题型很经常出现，而且变种的题型很多，那就是单调栈。在前几天我曾经有复盘过一题就是用单调栈解的最大矩形。今天我总共要梳理5题，其中三题就和单调栈相关，可见其重要程度。（另外两题是递归）而且我觉得单调栈说难也不是很难，其定义很容易理解，主要是要想如何利用单调栈的性质去解相关的题目，这点是比较不容易做到的。

1.递归函数逆序一个栈

题目：逆序一个栈：实现两个递归函数
1->每次从栈中取出最底层的元素
2->实现一个递归将取出最底层的最底层元素按后来先执行的顺序插入到栈中

思路：递归思想就是不断调用本身去重复执行类似的操作,说实话，我递归感觉也不是很熟悉。常见的递归比如说二叉树的遍历，以及斐波那契数列问题。这题将实现分成两步，就是上面提到的两点，首先将栈的最底层元素取出（其他元素不变）。然后对栈进行逆序。（通过递归实现）第一步递归：递归出口是将栈中最后一个元素返回，递归主体是往下取最后一个元素，将非最后一个元素再装回栈中。第二步递归则是先填后面的元素（栈顶靠后），再填最后的元素（栈底）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_last_and_remove(stack):
    """
    从栈中取出并删除栈底元素
    """
    item = stack.pop()
    if not stack:
        return item
    else:
        last = get_last_and_remove(stack)
        stack.append(item)
        return last

def reverse(stack):
    """
    对栈进行逆序
    """
    if not stack:
        return
    else:
        last = get_last_and_remove(stack)
        reverse(stack)
        stack.append(last)

2.用递归来求解汉诺塔问题

题目：用两种方法解决汉诺塔问题：
1,递归 2,非递归：栈
要求：
移动汉诺塔的过程中，不能直接从左移动到右，要先移动到mid，从右到左同理
打印出每一步移动的过程以及返回总步数
如 2层汉诺塔的移动过程:
move 1 from left to mid
move 1 from mid to right
move 2 from left to mid
move 1 from right to mid
move 1 from mid to left
move 2 from mid to right
move 1 from left to mid
move 1 from mid to right
It will take 8 steps

思路：这里限制了移动的方法，但实际上，思路还是差不多的，只不过需要考虑的情况变多了。原来的汉诺塔问题用递归方法求解是很好理解的。递归方法要知道在这一步递归中完成了那些事情，最重要的是要知道参数的具体含义，感觉有点和dp还有回溯类似。在原始的问题中，主要是要理解三个位置的性质转换，汉诺塔一共有三个柱子，分别是left位，mid位，以及right位，其中两个位置是from和to，剩下的一个则是tmp位，在子问题中，他们的性质会发生改变。在限制问题中，主要是要理解一共有几种情况，要对不同情况分别讨论。移动的可能性可以分成两种，一种是只要一步，也就是from和to是mid的时候；另一种是from和to不是mid的时候。

1
2
3
4
5
6
7
8
def move(n,a,b,c):   #n为圆盘数，a代表初始位圆柱，b代表过渡位圆柱，c代表目标位圆柱
	if n==1:
		print(a,'-->',c)
	else:
		move(n-1,a,c,b)   #将初始位的n-1个圆盘移动到过渡位，此时初始位为a，上一级函数的过渡位b即为本级的目标位，上级的目标位c为本级的过渡位
		print(a,'-->',c)
 
		move(n-1,b,a,c)   #将过渡位的n-1个圆盘移动到目标位，此时初始位为b，上一级函数的目标位c即为本级的目标位，上级的初始位a为本级的过渡位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def hanoiProblem(num:int, left:str ,mid:str ,right:str ,From:str ,to:str ):
    if num < 1:
        return 0
    else:
        return process(num,left,mid,right,From,to)


def process(num:int,left:str,mid:str,right:str,From:str,to:str):
    if num == 1:
        if From == 'mid' or to == 'mid':
            print('move 1 from ' + From + ' to ' + to)
            return 1
        else:
            print('move 1 from ' + From + ' to ' + 'mid')
            print('move 1 from '+'mid' + ' to ' + to)
            return 2
    if From == 'mid' or to == 'mid':
        another = 'right' if From == 'left' or to == 'left' else 'left'
        part1 = process(num-1,'left','mid','right',From,another)
        print('move ' + str(num) +' from ' + From + ' to ' + to)
        part2 = 1
        part3 = process(num-1,'left','mid','right',another,to)
        return part1 + part2 + part3
    else:
        part1 = process(num-1,'left','mid','right',From,to)
        print('move '+str(num) +' from '+From+' to ' + 'mid')
        part2 = 1
        part3 = process(num-1,'left','mid','right',to,From)
        print('move '+str(num) +' from '+' mid '+' to ' +to)
        part4 = 1
        part5 = process(num-1,'left','mid','right',From,to)
        return part1 + part2 + part3 + part4 + part5

3.滑动窗口的最值

题目：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路：这题在之前的面试中也出现过，我记得，最早之前。然后超时了。我那个时候好像没有用到单调栈，所以错了？这题需要我们维护一个长度最长为窗口大小的单调递减栈。单调栈我们之前介绍过，主要用来解需要关于i的向左或向右的第一个比他大或者小的位置信息，但在这一题中，用的是单调栈最原始的性质，那就是在栈底，永远是这个栈的最值，而且往后是这个栈的次最大值。代码的思路是用queue来维护这个单调栈，在入栈时，先判断栈顶是否已经超过窗口的范围，然后用单调栈的性质继续操作。最后判断当前的范围是否是窗口，然后添加结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        # queue存入num的位置信息
        queue,res,i = [],[],0
        while i < len(num) and size>0:
            # 如果queue【0】的位置信息过期就出队列
            if len(queue) > 0 and i-size+1 > queue[0]:
                queue.pop(0)
            # 弹出queue中所有比num【i】小的数字
            while len(queue) > 0 and num[queue[-1]] < num[i]:
                queue.pop()
            # 新的数是一定会入队列的
            queue.append(i)
            # 从第一个窗口开始添加最大值
            if i >= size-1:
                res.append(num[queue[0]])
            i += 1
        return res

4.构造数组的maxtree

题目：

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：

​ 6

​ / \

3 5
\ /
2 0

1

思路：这一题用的还是单调栈，这里就用了单调栈的另一个重要性质了，位置。我们这里引入两个哨兵，放在数组开头和结尾，简化一下代码逻辑。然后，我们还需要一个字典，用于储存数组对应的树节点，不然后面要描述节点之间的关系，就很难操作了。相信大家应该都还记得单调栈的主要针对的目标是弹出栈的那个元素吧，这里也是一样的，所以我们的代码主要就围绕这个被弹出栈的元素，一个元素被弹出栈，说明什么？说明有一个比他大的大哥来了，同时在栈里面在他旁边的那个元素也是比他大的，那这两个大哥到底谁是他的父节点呢？比一下就知道啦，谁比较小，谁就是他的父节点。（这里需要证明，略）然后我们总结一下规律，如果，选了左边的，那我就是他的右节点；选了右边的，那我就是他的左节点。最后由于一定有一个超级大哥，原始数组的元素都会被弹出栈，我们也就得到了所有的结果，最后被弹出的那个就是根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
    	  # 加入两个哨兵
        nums = [float('INF')]+nums+[float('INF')]
        tmp = []
        # 存储数组对应节点信息
        node_dict = {}
        for num in nums:
            node_dict[num] = TreeNode(num)
        # 最后进来的是超级大哥
        for i in range(len(nums)):
            if not tmp:
                tmp.append(i)
            else:
            		# 针对被弹出栈的元素
                while nums[tmp[-1]]<nums[i]:
                		# 一共有三种情况
                    k = tmp.pop()
                    if nums[tmp[-1]] < nums[i]:
                        node_dict[nums[tmp[-1]]].right = node_dict[nums[k]]
                    elif nums[tmp[-1]] > nums[i]:
                        node_dict[nums[i]].left = node_dict[nums[k]]
                    else:
                        return node_dict[nums[k]]
                # 最后一定记得是要入栈的
                tmp.append(i)

5.最大值减去最小值等于或者小于num的子数组数量

题目：给一个数组arr，求出所有arr的子数组的最大值减去最小值小于等于num的数量

思路：最优解：
1，维持最大值和最小值的双端队列（参考滑动窗口的最大值数组）
2，i<j 两个指针遍历arr找出以arr[i]为开头的数组个数j-i 先移动j的位置，再移动i的位置。这里需要证明的是当某个位置的j不满足条件时，后面的j一定是不满足条件的，所以可以略过，而在这个j之前的以i开头的数组都是满足条件的，所以是加上j-i。
3，将所有的j-i进行相加;每个元素分别进出一次队列并判断，总时间复杂度O(n)。

需要注意：是否入栈是需要判断的，因为在break的时候，虽然j位置的元素已经入栈了，但是j没有+1，（注意i往前走的时候，j不是重新来的。）因此，可能导致重复添加元素，所以需要判别j是否已经在栈中了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def get_max(arr: list, num : int):
    if not arr or len(arr) == 0 or num < 0:
        return 0
    qmax, qmin = [], []
    i = 0
    j = 0
    ret = 0
    while i < len(arr):
        while j < len(arr):
            if not qmin or qmin[-1] != j:
                while qmin and arr[qmin[-1]] >= arr[j]:
                    qmin.pop()
                qmin.append(j)
                while qmax and arr[qmax[-1]] <= arr[j]:
                    qmax.pop()
                qmax.append(j)
            if arr[qmax[0]] - arr[qmin[0]] > num:
                break
            j += 1
        ret += j - i
        # 如果超出范围的话就弹出
        if qmin[0] == i:
            qmin.pop(0)
        if qmax[0] == i:
            qmax.pop(0)
        i += 1

    return ret
请作者喝杯咖啡吧！