有符号整数溢出[C++]

ds97pgxw  于 2023-01-22  发布在  其他
关注(0)|答案(2)|浏览(171)

目标在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;
    }
};
7z5jn7bk

7z5jn7bk1#

我在一个编程挑战网站上也遇到了同样的问题,但在IDE上没有遇到“整数溢出”。“long long”数据类型在IDE上对我很有效。

qxsslcnc

qxsslcnc2#

根据我的理解,当你乘以INT_MIN * 2时,你的x是int,它超出了int的范围。因为int * int导致int。所以将x的数据类型改为long long int可能会解决这个问题。请看我在下面发布的代码,并做了一些修改。

class MinStack {
    stack<long long int> s;
    long long int mini;
public:
    MinStack() {
        mini = INT_MAX;
    }
    
    void push(int val) {
        long long nval = val;
        if (s.empty()) {
            mini = nval;
            s.push(nval);
            return;
        }
        else if (nval < mini) {
            s.push(2 * nval - mini);
            mini = nval;
        }

        else
            s.push(nval);
    }
    

};

相关问题