LintCode 12 带最小值操作的栈

2019-11-08 18:35:53

字体：大中小

来源：转载

供稿：网友

题目:MinStack

要求:

实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。注意事项如果堆栈中没有数字则不能进行min方法的调用

样例:

如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1

算法要求:

无

解题思路:

这道题有二种常规的算法，一种是额外用一个辅助栈存最小值；另一种就是将栈值都存为与最小值的差，因为一次只能出栈一个数，所以我们只需要适时的改变minNumber的值就可以了（第二种方法目前适用于数字），在push的时候，我们将小于当前最小值的数，存为负数，值为二数之差，这样在pop的时候就可以根据是否为负数来判断是否需要变为上一个最小值，即栈值为负数时，当前最小值为实际的栈值，负数的值为为比上一个最小值小多少。相当于，每个数都记录了上一个push前的最小值。下面给出第二种方法，第一种方法实现非常简单，请读者自行实现。

算法如下:

class MinStack {public: MinStack() { top = -1; numStack = new int[100]; } void push(int number) { if (top == 99) { throw top; } if (top == -1) {//第一次push的时候需要将第一个数设为最小值 minNumber = number; numStack[++top] = 0; } else if (number < minNumber) {//遇到了比当前最小值更小的数 numStack[++top] = number - minNumber; minNumber = number; } else {//储存与当前最小值的差值即可 numStack[++top] = number - minNumber; } } int pop() { if (top == -1) { throw top; } if (numStack[top] >= 0) {//这里为当值为正数时，其实际的值为最小值+差值 return numStack[top--] + minNumber; } else {//这是为负数时，其实际的值为最小值，再将最小值还原为上一次的最小值 minNumber = minNumber - numStack[top]; return minNumber + numStack[top--]; } } int min() { if (top == -1) { throw top; } return minNumber; } ~MinStack() { delete numStack; }PRivate: int *numStack; int top; int minNumber;};

上一篇：redis,win,cmd

下一篇：1002. A+B for Polynomials (25)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注