使用递归函数逆序一个栈

原题(来源:牛客网)

一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计一个算法实现逆序栈的操作,但是只能用递归函数来实现,而不能用另外的数据结构。

解法

思想

设计一个函数getAndRemoveLastElement用于获取并移除栈底元素,当栈空的时候进行回溯,并将获取的元素压入栈,就能达到逆序的效果。

这样做的时间复杂度肯定是没一个辅助队列来的快的,好处是没有使用额外的空间(除了递归栈空间)

时间复杂度计算:设栈的大小为n,每一次获取栈底元素的时间复杂度是O(n),栈的大小要从n->0,就是O(n)+O(n-1)+O(n-2)+...+O(1)=O(n^2)

代码

class Solution {
    public void reverse(Stack<Integer> stack){
        if(stack.isEmpty()){
            return;
        }
        //每次获取栈底元素,最后一次获取的即是栈顶元素
        int i = getAndRemoveLastElement(stack);
        reverse(stack);
        //回溯的时候将获取的元素压入
        stack.push(i);
    }

    public int getAndRemoveLastElement(Stack<Integer> stack){
        //获取并移除栈顶元素
        int result = stack.pop();
        //获取栈底元素
        if(stack.isEmpty()){
            return result;
        }else{
            int last = getAndRemoveLastElement(stack);
            //回溯的时候将获取的元素压入
            stack.push(result);
            return last;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e4%bd%bf%e7%94%a8%e9%80%92%e5%bd%92%e5%87%bd%e6%95%b0%e9%80%86%e5%ba%8f%e4%b8%80%e4%b8%aa%e6%a0%88/

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

相关推荐

  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170
  • leetcode1028-从先序遍历还原二叉树

    原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,…

    2020年6月18日
    02410
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    0100
  • leetcode2-两数相加

    原题 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回…

    算法 2019年12月17日
    080
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0400
  • leetcode46-全排列

    原题 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [   [1,2,3],   [1,3,…

    算法 2020年3月3日
    0180
  • leetcode117-填充每个节点的下一个右侧节点指针II

    原题 给定一个二叉树 struct Node {   int val;   Node *left;   Node *ri…

    2020年1月14日
    0370
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0220
  • leetcode53-最大子序和

    原题 原题 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4],…

    算法 2020年2月20日
    0130
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0150

发表回复

登录后才能评论