p2p网站开发价格,阜阳市重点工程建设局网站,网站建设宗旨,wordpress 分类目录404转载自 玻璃猫 程序员小灰 小灰回忆起当时的情景…… 题目#xff1a;实现一个栈#xff0c;带有出栈#xff08;pop#xff09;#xff0c;入栈#xff08;push#xff09;#xff0c;取最小元素#xff08;getMin#xff09;三个方法。要保证这三个方法的时间复杂度…转载自 玻璃猫 程序员小灰 小灰回忆起当时的情景…… 题目实现一个栈带有出栈pop入栈push取最小元素getMin三个方法。要保证这三个方法的时间复杂度都是O1。 小灰的想法 1.创建一个整型变量 min初始值-1 2.当第一个元素进栈时让min0即把唯一的元素当做最小值。 3.之后每当一个新元素近栈让新元素和min指向位置的元素比较大小。如果Stack[min]大于新元素则min等于新元素的下标Stack[min]小于新元素则不做改变。 4.当调用getMin方法的时候直接返回min所指向位置的元素即可。 按这个思路近栈、出栈、取最小值的时间复杂度都是O(1)空间复杂度也是O(1)。 回忆到此结束…… 解法 1.设原有的栈叫做栈A此时创建一个额外的栈B用于辅助原栈A。 2.当第一个元素进入栈A的时候让新元素的下标进入栈B。这个唯一的元素是栈A的当前最小值。考虑到栈中元素可能不是类对象所以B栈存储的是A栈元素的下标 3.每当新元素进入栈A时比较新元素和栈A当前最小值的大小如果小于栈A当前最小值则让新元素的下标进入栈B此时栈B的栈顶元素就是栈A当前最小值的下标。 4.每当栈A有元素出栈时如果出栈元素是栈A当前最小值则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的是栈A当中原本第二小的元素代替刚才的出栈元素成为了栈A的当前最小值。备胎转正 5.当调用getMin方法的时候直接返回栈B的栈顶所指向的栈A对应元素即可。 这个解法中近栈、出栈、取最小值的时间复杂度都是O(1)最坏情况空间复杂度是O(N)。 扩展题目 实现一个队列带有出队deQueue入队enQueue取最小元素getMin三个方法。要保证这三个方法的时间复杂度都尽可能小。 小灰回忆起当时的情景…… 题目实现一个栈带有出栈pop入栈push取最小元素getMin三个方法。要保证这三个方法的时间复杂度都是O1。 小灰的想法 1.创建一个整型变量 min初始值-1 2.当第一个元素进栈时让min0即把唯一的元素当做最小值。 3.之后每当一个新元素近栈让新元素和min指向位置的元素比较大小。如果Stack[min]大于新元素则min等于新元素的下标Stack[min]小于新元素则不做改变。 4.当调用getMin方法的时候直接返回min所指向位置的元素即可。 按这个思路近栈、出栈、取最小值的时间复杂度都是O(1)空间复杂度也是O(1)。 回忆到此结束…… 解法 1.设原有的栈叫做栈A此时创建一个额外的栈B用于辅助原栈A。 2.当第一个元素进入栈A的时候让新元素的下标进入栈B。这个唯一的元素是栈A的当前最小值。考虑到栈中元素可能不是类对象所以B栈存储的是A栈元素的下标 3.每当新元素进入栈A时比较新元素和栈A当前最小值的大小如果小于栈A当前最小值则让新元素的下标进入栈B此时栈B的栈顶元素就是栈A当前最小值的下标。 4.每当栈A有元素出栈时如果出栈元素是栈A当前最小值则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的是栈A当中原本第二小的元素代替刚才的出栈元素成为了栈A的当前最小值。备胎转正 5.当调用getMin方法的时候直接返回栈B的栈顶所指向的栈A对应元素即可。 这个解法中近栈、出栈、取最小值的时间复杂度都是O(1)最坏情况空间复杂度是O(N)。 扩展题目 实现一个队列带有出队deQueue入队enQueue取最小元素getMin三个方法。要保证这三个方法的时间复杂度都尽可能小。
