假设我们要处理的堆栈是这样的:
最初的回答:
6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8
在上面的表示中,栈仅由左值构建,右值[minvalue]仅用于说明目的,将存储在一个变量中。
实际问题是当最小值被删除时:此时我们如何知道下一个最小元素是什么,而不必遍历整个栈。
例如,在我们的堆栈中,当6弹出时,我们知道这不是最小元素,因为最小元素是2,因此我们可以安全地删除它而不更新我们的min值。
但是当我们弹出2时,我们可以看到最小值现在是2,如果这个值被弹出,那么我们需要将最小值更新为3。
点1:
现在,如果您仔细观察,我们需要从此特定状态[2,minvalue = 2]生成minvalue = 3。
或者,如果您在堆栈中深入,我们需要从此特定状态[3,minvalue = 3]生成minvalue = 7
或者,如果您在堆栈中继续深入,则需要从此特定状态[7,minvalue = 7]生成minvalue = 8
您是否在上述三种情况中注意到了共同之处?我们需要生成的值取决于两个相等的变量。正确的。
为什么会发生这种情况?因为当我们推送一些比当前minvalue小的元素时,我们基本上将该元素推入堆栈并在minvalue中更新相同的数字。
点2:
因此,我们基本上在堆栈和minvalue变量中存储了相同数字的副本。
我们需要专注于避免这种重复,并在堆栈或minvalue中存储一些有用的数据,以生成上述CASES中的先前最小值。
让我们关注当要存储的值小于最小值时应该在堆栈中存储什么。
让我们将此变量命名为y,因此现在我们的堆栈将如下所示:
6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8
我已将它们重命名为y1、y2、y3,以避免混淆,因为它们都具有相同的值。
第三点:
现在让我们试着找出一些关于y1、y2和y3的限制条件。
你还记得我们何时需要在pop()时更新minvalue吗?只有当我们弹出的元素等于minvalue时才需要更新。
如果我们弹出的是大于minvalue的元素,则不需要更新minvalue。
因此,为了触发minvalue的更新,y1、y2和y3应该小于它们对应的minvalue。[我们避免相等以避免重复[点2]] 所以约束条件是[y < minValue]。
现在让我们回到填充y,我们需要在push时生成一些值并放入y中,请记住。
让我们将要推送的值x取为小于prevMinvalue的值,并将我们实际推送到堆栈中的值取为y。
所以显然新的MinValue=x,而y < newMinvalue。
现在我们需要计算y(记住y可以是任何小于newMinValue(x)的数字),以帮助我们满足约束条件,使用prevMinvalue和x(newMinvalue)。
Let's do the math:
x < prevMinvalue [Given]
x - prevMinvalue < 0
x - prevMinValue + x < 0 + x [Add x on both side]
2*x - prevMinValue < x
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].
如果在推入x的时候它小于prevMinValue,那么我们就推入y[2*x-prevMinValue]并更新newMinValue = x。
而当弹出时,如果栈中包含小于minValue的元素,那么这就是我们更新minValue的时机。我们需要从curMinValue和y计算prevMinValue。
y = 2*curMinValue - prevMinValue [已证明]
prevMinValue = 2*curMinvalue - y。
2*curMinValue - y 是我们现在需要更新为prevMinValue的数字。
以下是采用相同逻辑的代码,时间复杂度为O(1),空间复杂度为O(1)。
#include <bits/stdc++.h>
using namespace std;
struct MyStack
{
stack<int> s;
int minEle;
void getMin()
{
if (s.empty())
cout << "Stack is empty\n";
else
cout <<"Minimum Element in the stack is: "
<< minEle << "\n";
}
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
int t = s.top();
cout << "Top Most Element is: ";
(t < minEle)? cout << minEle: cout << t;
}
void pop()
{
if (s.empty())
{
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
if (t < minEle)
{
cout << minEle << "\n";
minEle = 2*minEle - t;
}
else
cout << t << "\n";
}
void push(int x)
{
if (s.empty())
{
minEle = x;
s.push(x);
cout << "Number Inserted: " << x << "\n";
return;
}
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "\n";
}
};
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
return 0;
}