关于leetcode:栈和排序

栈和排序

跟多题解，关注公众号【程序员学长】，送你上百本经典计算机电子书

问题形容

给你一个由 1~n，n 个数字组成的一个排列和一个栈，要求依照排列的程序入栈。如何在不打乱入栈程序的状况下，仅利用入栈和出栈两种操作，输入字典序最大的出栈序列。

排列：指 1 到 n 每个数字呈现且仅呈现一次。

示例：

输出：[2,1,5,3,4]

输入：[5,4,3,1,2]

剖析问题

因为咱们只能应用出栈和入栈两种操作，要想使得出栈序列字典序最大，首先想到的就是令高位尽可能地大，咱们出栈的机会就是：以后入栈元素若是大于之后将要入栈的元素，那么就将其出栈。当元素出栈后，还须要判断栈顶元素与之后将要入栈元素之间的大小关系，如果此时栈顶元素大于之后将要入栈的元素，那么就将其出栈，一直判断直到栈为空或条件不满足。

为了疾速判断“以后入栈元素是否大于之后将要入栈的元素”，咱们须要创立一个辅助数组 temp，其中 temp[i] 示意 i 之后的最大元素。借助辅助数组，咱们能够以 O(1) 的工夫复杂度去判断以后入栈元素是否大于之后将要入栈的元素。

上面咱们来看一下代码的实现。

import sys
class Solution:
    def solve(self , a):
        n=len(a)
        res=[]
        if n==0:
            return res
        stack=[]
        temp=[0]*n
        temp[n-1]=-sys.maxsize-1
        #从右往左遍历数组 a, 而后取填充 temp
        #使得 temp[i] 示意 i 之后的最大元素
        for i in range(n-2,-1,-1):
            temp[i]=max(a[i+1],temp[i+1])

        #遍历数组 a
        for i in range(0,n):
            if a[i] > temp[i]:  #若以后元素大于之后将要入栈的元素, 将其退出后果中
                res.append(a[i])
                # 若栈不为空，且栈顶元素大于 temp[i],
                # 栈顶出栈，退出后果中
                while stack and stack[-1] > temp[i]:
                    res.append(stack[-1])
                    stack.pop()
            else:
                stack.append(a[i])

        while stack:
            res.append(stack[-1])
            stack.pop()
        return res

该算法的工夫复杂度是 O(n)，空间复杂度也是 O(n)。