堆栈中的剩余数字.md

堆栈中的剩余数字

华为机试

向一个空栈中依次存入正整数， 假设入栈元素n(1<=n<=2^31-1)按顺序依次为nx...n4、n3、n2、n1, 每当元素入栈时，如果n1=n2+...+ny(y的范围[2,x]，1<=x<=1000)，则n1~ny全部元素出栈，重新入栈新元素m(m=2*n1)。

如：依次向栈存入6、1、2、3, 当存入6、1、2时，栈底至栈顶依次为[6、1、2]；当存入3时，3=2+1，3、2、1全部出栈，重新入栈元素6(6=2*3)，此时栈中有元素6；因为6=6，所以两个6全部出栈，存入12，最终栈中只剩一个元素12。

输入描述: 使用单个空格隔开的正整数的字符串，如"5 6 7 8"， 左边的数字先入栈，输入的正整数个数为x，1<=x<=1000。

输出描述: 最终栈中存留的元素值，元素值使用空格隔开，如"8 7 6 5"， 栈顶数字在左边。

示例1 

输入：5 10 20 50 85 1 

输出：1 170

说明 5+10+20+50=85， 输入85时，5、10、20、50、85全部出栈，入栈170，最终依次出栈的数字为1和170。

解法

一开始以为是直接法，元素num依次入栈，从栈顶往下累加看能否等于n，能则消消乐全弹出，压入2*num

后来发现遗漏了压栈之后继续消消乐的情况（如题目的6、1、2、3），加入递归处理

alist = list(map(int, input().split(' ')))
stack = []
# 辅助函数，将num压入栈
def addToStack(num):
    global stack #全局栈
    i = len(stack)-1 	#栈顶
    sum = 0
    while i >= 0 and sum+stack[i] <= num:
        sum += stack[i]
        i -= 1
    if sum == num:
        stack = stack[:i+1]
        addToStack(2*num)	#符合则继续递归消消乐
    else:
        stack.append(num)	#否则直接压栈

for num in alist:	#对每个数执行一次压栈
    addToStack(num)

for i in stack[::-1]:	#输出
    print(str(i) + ' ', end="")