min
变量保存最小值,每次push操作压栈时,保存的是入栈的值和最小值min的差值,而不是入栈的值;pop出栈时,通过min
值和栈顶的值得到;不过此算法有一个缺陷,两数差值有溢出风险。Number.MAX_VALUE
。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
数组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
数组queue
,因此,空间复杂度是