栈和排序

栈和排序_牛客题霸_牛客网

问题简述

给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈
你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列

要求：时间复杂度 O(n)，空间复杂度 O(n)

思路1

• 题目要求字典序最大，且数组中的元素确定为 1~n；

• 因此第一个出栈的元素一定是 n；

• 假设当前出栈元素为 a[i]，则接下来有两种情况：

  • 如果当前栈顶元素大于 a[i] 之后的最大值，则循环出栈；

  • 否则继续入栈；

• 写法 1 为上述算法的直观实现（每次查找 a[i+1:n] 中的最大值），会超时；

• 写法 2 预处理了每个位置之后的最大值（不包含当前位置）；

• 写法 3 是本质上也是上述算法的实现，但是技巧性更强（只遍历一次）；

  • 它利用了题目中数组中元素为 1~n 这一特点；如果不是这些元素就会出问题；

Python 写法1（超时）

class Solution:
    def solve(self , a: List[int]) -> List[int]:
        
        n = len(a)
        
        s = []  # 模拟栈
        ret = []  # 保存答案
        for i in range(n):
            s.append(a[i])
            # 如果栈顶元素大于之后的最大值，就出栈，否则跳过
            while s and s[-1] >= (mx := max(a[i + 1:] + [float('-inf')])):  # 防止 max(空数组)
                ret.append(s.pop())
        
        while s:
            ret.append(s.pop())
        
        return ret

Python 写法2（推荐）

class Solution:
    def solve(self , a: List[int]) -> List[int]:
        
        n = len(a)
        # 预处理：计算当前位置之后的最大值（不包括当前位置）
        book = [0] * n
        book[-1] = float('-inf')
        for i in range(n - 2, -1, -1):
            book[i] = max(book[i + 1], a[i + 1])
            # book[i] = max(book[i + 1], a[i])  # 这样写表示包括当前位置，err
        
        s = []  # 模拟栈
        ret = []  # 保存答案
        for i in range(n):
            s.append(a[i])
            while s and s[-1] >= book[i]:  # book[i] 表示 a[i] 之后的最大值
                ret.append(s.pop())
        
        while s:
            ret.append(s.pop())
        
        return ret

Python 写法3

class Solution:
    def solve(self , a: List[int]) -> List[int]:
        
        ret = []  # 记录答案    
        s = []    # 模拟栈
        n = len(a)
        book = [0] * (n + 1)  # 记录已经出现过的元素
        
        for x in a:
            s.append(x)
            book[x] = 1
            while n and book[n]:
                n -= 1
            while s and n <= s[-1]:
                ret.append(s.pop())
        
        while s:
            ret.append(s.pop())
        return ret