用一个栈实现另一个栈的排序

原题(来源牛客网)

一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序?

解法

思想

申请一个辅助栈,应让该辅助栈成为一个单调栈,可以这样做:

原栈每次弹出一个元素,如果比辅助栈顶元素小(或辅助栈内为空)就直接压入辅助栈,如果比辅助栈顶元素大,则先保留该元素,将辅助栈内的比该元素小的元素压回原栈,再将该元素压入辅助栈,如此往复,直到辅助栈成为一个栈顶到栈底递增的栈,再将辅助栈内的元素压回原栈。

代码

class Solution {
    public void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<>();
        while(!stack.isEmpty()){
            int cur = stack.pop();
            while(!help.isEmpty()&&help.peek()<cur){
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while(!help.isEmpty()){
            stack.push(help.pop());
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%94%a8%e4%b8%80%e4%b8%aa%e6%a0%88%e5%ae%9e%e7%8e%b0%e5%8f%a6%e4%b8%80%e4%b8%aa%e6%a0%88%e7%9a%84%e6%8e%92%e5%ba%8f/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月20日
下一篇 2020年4月21日

相关推荐

  • leetcode344-反转字符串

    原题 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间…

    算法 2019年11月18日
    0150
  • leetcode82-删除排序链表中的重复元素II

    原题 给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示…

    算法 2020年5月31日
    0240
  • 剑指offer50-第一个只出现一次的字符

    原题(来源Leetcode) 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s…

    算法 2020年6月10日
    0180
  • 剑指offer03-数组中重复的数字

    原题(来源Leetcode) 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,…

    算法 2020年3月13日
    0140
  • leetcode343-整数拆分

    原题 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1…

    算法 2020年4月13日
    0110
  • leetcode40-组合总和II

    原题 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字…

    算法 2020年5月2日
    0730
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    070
  • leetcode572-另一个树的子树

    原题 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树…

    算法 2020年5月8日
    0380
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01560
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170

发表回复

登录后才能评论