ACM题 列车长的烦恼,在此我只要求帮我分析 答案问我自己有

2025-02-27 05:46:59
推荐回答(1个)
回答1:

这个题目就是判断出栈序列是否合法:
分析:关于栈有一个很有用的性质,对于出栈序列的每一个元素,该元素后比该元素先入栈的一定按照降序排列。若入栈的是一串数字例如12345,则21435是一个合法的出栈顺序,每一个元素i后比i小的都是降序排列(因为入栈的数字代表了进栈先后),24153不是合法的,因为对于4,比它小的1和3的顺序不对。
即一句话:出栈序列中,元素i之后所有比i小的元素间必须是降序排列的。