目标在O(1)时间复杂度内找到栈中的最小值。
问题:在某些Leetcode测试用例中,以下操作(2*x-minEle)失败。
实际错误-运行时错误:有符号整数溢出:2 * -2147483648不能在类型“int”中表示
我尝试用long long数据类型替换每个整数值,但仍然得到相同的错误
代码如下:
class MinStack {
public:
int minEle = INT_MAX;
vector<int> s;
void push(int x) {
if(s.empty())
{
minEle=x;
s.push_back(x);
return;
}
if(x<minEle)
{
s.push_back(2*x-minEle);
minEle = x;
}
else
s.push_back(x);
}
void pop() {
int y = s.back();
if(y<minEle)
{
minEle = 2*minEle - y;
}
s.pop_back();
}
int top() {
return s.back();
}
int getMin() {
return minEle;
}
};
2条答案
按热度按时间7z5jn7bk1#
我在一个编程挑战网站上也遇到了同样的问题,但在IDE上没有遇到“整数溢出”。“long long”数据类型在IDE上对我很有效。
qxsslcnc2#
根据我的理解,当你乘以INT_MIN * 2时,你的x是int,它超出了int的范围。因为int * int导致int。所以将x的数据类型改为long long int可能会解决这个问题。请看我在下面发布的代码,并做了一些修改。