4_6双栈排序

请编写一个程序,按升序对栈进行排序(即最大元素位于栈顶),要求最多只能使用一个额外的栈存放临时数据,但不得将元素复制到别的数据结构中。

给定一个int[] numbers(C++中为vector&ltint>),其中第一个元素为栈顶,请返回排序后的栈。请注意这是一个栈,意味着排序过程中你只能访问到第一个元素。

测试样例:
输入:[1,2,3,4,5]
返回:[5,4,3,2,1]

class TwoStacks {
public:
    vector<int> twoStacksSort(vector<int> numbers) {
        // write code here
        vector<int> help;
        help.push_back(numbers.back());
        numbers.pop_back();
        while(!numbers.empty()){
            int curr = numbers.back();
            numbers.pop_back();
            if(curr <= help.back()){
                help.push_back(curr);
            }else{
                do{
                    numbers.push_back(help.back());
                    help.pop_back();
                }while(help.back() < curr && !help.empty());
                help.push_back(curr);
            }
        }
        return help;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容