原题（来源：牛客网）
一个栈依次压入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/
相关推荐
-
leetcode1248-统计「优美子数组」
原题 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 ...
-
leetcode658-找到K个最接近的元素
原题 给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较...
-
leetcode191-位1的个数
原题 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。 示例 1： 输入： 000000000000000000000000...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
-
leetcode435-无重叠区间
原题 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没...
-
leetcode28-实现strStr()
原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从...
-
leetcode151-翻转字符串里的单词
原题 给定一个字符串，逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he...
-
leetcode14-最长公共前缀
原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...
-
剑指offer46-把数字翻译成字符串
原题 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编...
-
leetcode744-寻找比目标字母大的最小字母
原题 给定一个只包含小写字母的有序数组letters 和一个目标字母 target，寻找有序数组里面比目标字母大的最小字母。 数组里字母的顺序是循环的。举个例子，如果目标字母tar...