最小栈、Shuffle an Array和将有序数组转换为二叉搜索树

最小栈
设计一个支持 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];
};
复杂度分析
时间复杂度：O(1)O(1)O(1)​
push、pop、top、getMin 操作都是基于数组索引，耗费 O(1) 的时间。
空间复杂度：O(n)O(n)O(n)​
每次 push 一个元素到 stack 栈的同时将 stack 栈中最小元素 push 到 minStack 栈，耗费O(n)O(n)O(n)的栈空间
方法二  差值存储
思路
用一个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;
};
复杂度分析
时间复杂度：O(1)O(1)O(1)​
空间复杂度：O(1)O(1)O(1)​
每次 push 一个元素到 stack 栈的同时只需要一个元素空间存储最小值，耗费O(1)O(1)O(1)的栈空间
Shuffle an Array
打乱一个没有重复元素的数组。
示例
// 以数字集合 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;
};
复杂度分析
时间复杂度：O(n2)O(n^2)O(n2)​
js 中 splice 方法的时间复杂度为 O(n)O(n)O(n)，因为当你在中间删除一个元素后，在此位置之后的所有元素都需要整体向前移动一个位置，因此导致遍历所有 nnn 个元素，又因为 splice 方法于 for 循环中需执行 nnn 遍，因此为 O(n2)O(n^2)O(n2)。
空间复杂度：O(n)O(n)O(n)​
为实现重置功能，原始数组需保存一份，因此为 O(n)O(n)O(n)。
方法二
思路
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;
};
复杂度分析
时间复杂度：O(n)O(n)O(n)​
上述算法中，for 循环内操作都是常数时间复杂度，因此为 O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)​
为实现重置功能，原始数组需保存一份，因此为 O(n)O(n)O(n)。
将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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;
  }
};
复杂度分析
时间复杂度：O(n)O(n)O(n)​
每次调用需要遍历数组，因此，时间复杂度是 O(n)O(n)O(n)。
空间复杂度：O(1)O(1)O(1)​
算法在运行过程中，只申请了常量大小内存，因此，空间复杂度是 O(1)O(1)O(1)。
方法二 数组模拟队列
思路
可以先将提示数组按照二分法的查找顺数，一次推入数组中。然后，按照数组顺序通过生成二叉树的一般算法生成目标树。由于在题目的二叉树中，节点的左子节点的值要小于节点的值，节点的右子节点的值要大于节点的值。因此，数组从中点按照 [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 = [];
  // 二分法重新排列数组 queue
  initNodeValueArr(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);
  }
};
复杂度分析
时间复杂度：O(n)O(n)O(n)​
每次调用需要遍历数组，因此，时间复杂度是 O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)​
算法在运行过程中，申请了 n 长度的数组 queue，因此，空间复杂度是 O(n)O(n)O(n)​