设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例
MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2.
思路
根据数组的性质,push、pop、top都能在常数时间内完成,而此题关键是常数时间内检索最小元素,此解法是开辟一个数组存储,push数据同时,存储当前栈中最小元素,pop数据的同时pop最小元素栈栈顶数据;
详解
创建最小元素栈时,开辟 stack 及 minStack 数组,stack 用于存储压栈元素,minStack 用于存储最小元素序列;
push操作执行元素 x 压栈:
如果 minStack 数组为空时,添加元素 x 到 minStack 数组。
否则比较元素 x 与数组末尾元素,取最小值添加到 minStack 数组末尾。表示当前栈中元素的最小值为x。
pop操作:
删除 stack 数组末尾元素的同时,删除数组 minStack 末尾元素。
getMin操作:
直接调用 pop 方法,返回 minStack 数据中末尾元素即可。
const MinStack = function () {this.stack = [];this.minStack = [];};/*** @param {number} x* @return {void}*/MinStack.prototype.push = function (x) {this.stack.push(x);if (this.minStack.length === 0) {this.minStack.push(x);} else {const min = Math.min(this.minStack[this.minStack.length - 1], x);this.minStack.push(min);}};/*** @return {void}*/MinStack.prototype.pop = function () {this.minStack.pop();return this.stack.pop();};/*** @return {number}*/MinStack.prototype.top = function () {return this.stack[this.stack.length - 1];};/*** @return {number}*/MinStack.prototype.getMin = function () {return this.minStack[this.minStack.length - 1];};
复杂度分析
时间复杂度:
push、pop、top、getMin 操作都是基于数组索引,耗费 O(1) 的时间。
空间复杂度:
每次 push 一个元素到 stack 栈的同时将 stack 栈中最小元素 push 到 minStack 栈,耗费的栈空间
思路
用一个min
变量保存最小值,每次push操作压栈时,保存的是入栈的值和最小值min的差值,而不是入栈的值;pop出栈时,通过min
值和栈顶的值得到;不过此算法有一个缺陷,两数差值有溢出风险。
详解
创建最小元素栈时,开辟 stack 数组,用于存储入栈元素x与最小元素 min 的差值;同时定义变量 min,用于存储最小值,初始值为 Number.MAX_VALUE
。
push 操作执行元素x入栈::
取元素 x 与最小元素 min 的差值,压入stack数组:
比较元素x与min值,取其最小值赋值给min变量。
pop操作:
弹出stack数组末尾元素值 value,如果值value > 0,说明push操作的值大于 min,返回 value + min 值;如果值value <= 0,说明 push 操作的值小于等于原 min 值,恢复最小值min,同时返回 min 值即可。
top 操作:
取stack数组末尾元素值 value,如果值 value > 0,说明push操作的值大于min,返回 value + min 值;如果值 value <= 0,说明 push 操作的值小于等于原 min 值,返回 min 值即可。
getMin 操作:
返回 min 元素即可。
const MinStack = function () {this.stack = [];this.min = Number.MAX_VALUE;};/*** @param {number} x* @return {void}*/MinStack.prototype.push = function (x) {const min = this.min;this.stack.push(x - min);if (x < min) {this.min = x;}};/*** @return {void}*/MinStack.prototype.pop = function () {const value = this.stack.pop();const min = this.min;if (value > 0) {return value + min;} else {this.min = min - value;return min;}};/*** @return {number}*/MinStack.prototype.top = function () {const value = this.stack[this.stack.length - 1];if (value > 0) {return value + this.min;} else {return this.min;}};/*** @return {number}*/MinStack.prototype.getMin = function () {return this.min;};
复杂度分析
时间复杂度:
空间复杂度:
每次 push 一个元素到 stack 栈的同时只需要一个元素空间存储最小值,耗费的栈空间
打乱一个没有重复元素的数组。
示例
// 以数字集合 1, 2 和 3 初始化数组。int[] nums = {1,2,3};Solution solution = new Solution(nums);// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。solution.shuffle();// 重设数组到它的初始状态[1,2,3]。solution.reset();// 随机返回数组[1,2,3]打乱后的结果。solution.shuffle();
思路
reset
函数:缓存传入的原始数据,用于在函数调用时返回。但值得一提的是,进行缓存原始数据时,必须进行浅拷贝,因为原始数据为数组,普通的赋值会导致引用对象传递,一旦变更了 this.nums 的数组内容,缓存的数组也将同步变更
shuffle
函数:我们模拟一个这样的场景,有 n 个标着数的球,我们把这 n 个球放入一个看不见的袋子中,每次从中摸一个球出来,并按照摸出的顺序,直到摸空袋子。具体的操作,我们把原始数组复制一份为 nums,每次根据 nums 的长度随机生成一个下标从 nums 中取一个数出来,将其放入新数组 ary 中,并删除 nums 中对应下标的数
详解
定义 this.nums
存储传入的数据
定义 this.original
存储 nums
的克隆数组
定义重置 reset
方法,将 this.nums
重制为 this.original
的克隆数组,并将 this.original
重新克隆一遍(因数组为引用对象,不重新缓存新数组会导致 this.original
和 this.nums
同步变化)
定义打乱 shuffle
方法,根据 this.nums
的长度进行循环,每次从根据 this.nums
长度通过 Math.random()
随机生成一个下标
根据随机生成的下标,将值存入 ary
数组中
最后返回 ary
数组
代码
/*** @param {number[]} nums*/const Solution = (nums) => {this.nums = nums;this.original = nums.slice(0);};/*** 重置数组并返回* @return {number[]}*/Solution.prototype.reset = () => {this.nums = this.original;this.original = this.original.slice(0);return this.original;};/*** 返回一个随机重排的数组* @return {number[]}*/Solution.prototype.shuffle = () => {const ary = [];const nums = this.nums.slice(0);const len = nums.length;for (let i = 0; i < len; i += 1) {const targetIndex = Math.floor(Math.random() * nums.length);ary[i] = nums[targetIndex];nums.splice(targetIndex, 1);}return ary;};
复杂度分析
时间复杂度:
js 中 splice 方法的时间复杂度为 ,因为当你在中间删除一个元素后,在此位置之后的所有元素都需要整体向前移动一个位置,因此导致遍历所有 个元素,又因为 splice 方法于 for 循环中需执行 遍,因此为 。
空间复杂度:
为实现重置功能,原始数组需保存一份,因此为 。
思路
reset
函数:同方法一
shuffle
函数:为降低方法一中的时间复杂度,我们可以让数组中的元素进行互换,从而减少 splice 方法所需执行的时间。具体的操作,我们从数组的最后往前迭代,生成一个范围在 0 到当前遍历下标之间的随机整数,和当前遍历下标的元素进行互换。这跟方法一中的模拟摸球是一样的,每次被摸出的球便不能再被摸出来。
详解
定义 this.nums
存储传入的数据
定义 this.original
存储 nums
的克隆数组
定义重置 reset
方法,将 this.nums
重制为 this.original
的克隆数组,并将 this.original
重新克隆一遍(因数组为引用对象,不重新缓存新数组会导致 this.original
和 this.nums
同步变化)
定义打乱 shuffle
方法,根据 this.nums
的长度进行倒序循环,每次从根据当前下标 i
通过 Math.floor(Math.random() * (i + 1))
随机生成一个下标(Knuth-Durstenfeld Shuffle算法)
根据随机生成的下标,和当前下标,进行数据互换
最后返回 nums
数组
代码
/*** @param {number[]} nums*/const Solution = (nums) => {this.nums = nums;this.original = nums.slice(0);};/*** 重置数组并返回* @return {number[]}*/Solution.prototype.reset = () => {this.nums = this.original;this.original = this.original.slice(0);return this.original;};/*** 返回一个随机重排的数组* @return {number[]}*/Solution.prototype.shuffle = () => {const nums = this.nums.slice(0);const len = nums.length;for (let i = len - 1; i > 0; i -= 1) {const targetIndex = Math.floor(Math.random() * (i + 1));const tmp = nums[i];nums[i] = nums[targetIndex];nums[targetIndex] = tmp;}return nums;};
复杂度分析
时间复杂度:
上述算法中,for 循环内操作都是常数时间复杂度,因此为 。
空间复杂度:
为实现重置功能,原始数组需保存一份,因此为 。
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例
给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:0/ \-3 9/ \ / \-10 null 5 null
思路
由于数组是按照递增有序排列的,并且高度平衡二叉搜索树(一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1),可以使用二分法从数组的中间开始查找数据。
详解
找出数组的中间坐标(mid)对应元素,作为当前二叉树节点(root)的 value
root 的左节点 是 0 -> mid 的中间坐标对应元素
root 的右节点 是 mid -> (arr.length - 1) 的中间坐标对应元素
root 的左右节点 按照 1 - 3 步骤生成新的左右节点,直到数组遍历完,算法终止
代码
const sortedArrayToBST = (arr) => {return initTreeNodes(arr, arr.length - 1, 0);};const initTreeNodes = (arr, end, start) => {if (start <= end) {const mid = start + parseInt((end - start) / 2, 10);const root = Node(arr[mid]);root.left = initTreeNodes(arr, mid - 1, start);root.right = initTreeNodes(arr, end, mid + 1);return root;} else {return null;}};
复杂度分析
时间复杂度:
每次调用需要遍历数组,因此,时间复杂度是 。
空间复杂度:
算法在运行过程中,只申请了常量大小内存,因此,空间复杂度是 。
思路
可以先将提示数组按照二分法的查找顺数,一次推入数组中。然后,按照数组顺序通过生成二叉树的一般算法生成目标树。由于在题目的二叉树中,节点的左子节点的值要小于节点的值,节点的右子节点的值要大于节点的值。因此,数组从中点按照 [root, 左, 右, 左, 右...] 接收节点的值,并按照生成二叉树的一般算法,即可生成目标树。
详解
首先,使用二分法,先找到数组中间位置(mid)元素,将该元素 push 进目标数组 queue(模拟队列)
将数组分成两部分 0 -> mid, (mid + 1) -> arr.length
将获得两个新数组,按照 1、2 步骤重复,直到数组元素全部遍历完成
然后,按顺序遍历数组,arr[0]为 根节点值
当 queue[i], 小于 arr[0] 时会被分配到左子节点,大于 arr[0] 时会被分配到右子节点
当左子节点已经有值时,会比较左子节点的值与 queue[i],按照值得大小 分配到 左子节点的 左子节点或者 右子节点
当右子节点已经有值时,会比较右子节点的值与 queue[i],按照值得大小 分配到 左子节点的 左子节点或者 右子节点
遍历 queue, 重复执行 6、7 步骤, 直到 queue 被全部遍历
代码
const sortedArrayToBST = (arr) => {if (!arr.length) {return null;}const queue = [];// 二分法重新排列数组 queueinitNodeValueArr(arr, 0, arr.length, queue);// 根节点const root = new TreeNode(queue[0]);for (let i = 1; i < queue.length; i += 1) {// 插入节点数据insertNode(root, queue[i]);}return root;};const insertNode = (node, value) => {// 生成左子节点if (value < node.val) {if (!node.left) {node.left = new TreeNode(value);} else {insertNode(node.left, value);}// 生成右子节点} else if (!node.right) {node.right = new TreeNode(value);} else {insertNode(node.right, value);}};const initNodeValueArr = (arr, start, end, queue) => {const mid = start + parseInt((end - start) / 2, 10);queue.push(arr[mid]);// 左节点数值if (start < mid) {initNodeValueArr(arr, start, mid, queue);}// 右节点数值if (mid + 1 < end) {initNodeValueArr(arr, mid + 1, end, queue);}};
复杂度分析
时间复杂度:
每次调用需要遍历数组,因此,时间复杂度是 。
空间复杂度:
算法在运行过程中,申请了 n 长度的数组 queue
,因此,空间复杂度是