LintCode 12 帶最小值操作的棧

2019-11-08 18:35:53

字體：大中小

供稿：網(wǎng)友

題目:MinStack

要求:

實(shí)現(xiàn)一個(gè)帶有取最小值min方法的棧，min方法將返回當(dāng)前棧中的最小值。你實(shí)現(xiàn)的棧將支持push，pop 和 min 操作，所有操作要求都在O(1)時(shí)間內(nèi)完成。注意事項(xiàng)如果堆棧中沒有數(shù)字則不能進(jìn)行min方法的調(diào)用

樣例:

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

算法要求:

無

解題思路:

這道題有二種常規(guī)的算法，一種是額外用一個(gè)輔助棧存最小值；另一種就是將棧值都存為與最小值的差，因?yàn)橐淮沃荒艹鰲Ｒ粋€(gè)數(shù)，所以我們只需要適時(shí)的改變minNumber的值就可以了（第二種方法目前適用于數(shù)字），在push的時(shí)候，我們將小于當(dāng)前最小值的數(shù)，存為負(fù)數(shù)，值為二數(shù)之差，這樣在pop的時(shí)候就可以根據(jù)是否為負(fù)數(shù)來判斷是否需要變?yōu)樯弦粋€(gè)最小值，即棧值為負(fù)數(shù)時(shí)，當(dāng)前最小值為實(shí)際的棧值，負(fù)數(shù)的值為為比上一個(gè)最小值小多少。相當(dāng)于，每個(gè)數(shù)都記錄了上一個(gè)push前的最小值。下面給出第二種方法，第一種方法實(shí)現(xiàn)非常簡(jiǎn)單，請(qǐng)讀者自行實(shí)現(xiàn)。

算法如下:

class MinStack {public: MinStack() { top = -1; numStack = new int[100]; } void push(int number) { if (top == 99) { throw top; } if (top == -1) {//第一次push的時(shí)候需要將第一個(gè)數(shù)設(shè)為最小值 minNumber = number; numStack[++top] = 0; } else if (number < minNumber) {//遇到了比當(dāng)前最小值更小的數(shù) numStack[++top] = number - minNumber; minNumber = number; } else {//儲(chǔ)存與當(dāng)前最小值的差值即可 numStack[++top] = number - minNumber; } } int pop() { if (top == -1) { throw top; } if (numStack[top] >= 0) {//這里為當(dāng)值為正數(shù)時(shí)，其實(shí)際的值為最小值+差值 return numStack[top--] + minNumber; } else {//這是為負(fù)數(shù)時(shí)，其實(shí)際的值為最小值，再將最小值還原為上一次的最小值 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)