题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31,2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

首先我们考虑一个普通的正整数如何进行反转。

例如 1234。

最直接暴力的：字符串异常法。先将其转化为字符串，然后对字符串遍历，利用栈结构进行反转，反转之后的字符串类型强制转换成整数，抛出异常则溢出。这样可以处理1234这样的正整数。但是遇到负数就行不通了。

我们得考虑如何对负数进行反转，其实也很简单，只需要先判断输入数的正负性，然后记一个标记，同样的方式反转完成后，如果是负数，则拼接上负号-再进行强制类型转换，这样就可以解决了。

来看下这种“暴力字符串异常法”的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int convertStringToReverse(int x) {
    // 是否小于0
    boolean flag = x < 0;
    // 取绝对值转字符串
    String s = String.valueOf(Math.abs(x));
    // 转换成char数组进行遍历
    char[] chars = s.toCharArray();
    // 声明栈
    Deque<Character> stack = new LinkedList<>();
    // 入栈
    for (char aChar : chars) {
        stack.push(aChar);
    }
    StringBuilder res = new StringBuilder();
    if (flag) {
        // x值小于0，前面拼接上负号
        res.append("-");
    }
    // 出栈
    while (!stack.isEmpty()) {
        res.append(stack.pop());
    }
    try {
        // 强制类型转换
        return Integer.parseInt(res.toString());
    } catch (Exception e) {
        // 异常表示溢出
        return 0;
    }
}

这种做法，入栈遍历的时间复杂度O(n)，栈结构的空间复杂度O(n)，出栈遍历的时间复杂度O(n)。整体的时间复杂度是O(n)，空间复杂度O(n)。

显然，这种解法并不是最优解。

不做类型转换，只操作整数进行反转。如何操作？其实可以套用生产者消费者的思想。

对于输入整数x：

生产者逻辑：

获取整数的个位数字：n = x % 10。

消费者逻辑：

整个过程开始之前，反转结果res的初始值等于0。

将生产者产出的个位数加到res后面：res = res * 10 + n。

将输入整数的个位数去除：x /= 10。

当消费到x = 0时，整个过程结束，最终的res即为反转结果。

看似完美，但题意中说到了整数溢出。反转之后的范围为：[-2^31,2^31 - 1]，我们需要去考虑溢出的边界。

反转结果res每次消费都会增大一个数量级，我们来看下限制的数值范围：[-2147483648,2147483647]

对于反转结果res：

首先分析正数区间，考虑倒数第二位，如果本次消费前res > 214748364（即去掉正区间最大值的最后一位），无论此次消费到的个位数n为多少都溢出了；另一种情况，考虑最后一位，如果本次消费前res = 214748364，那本次消费时n值只要大于7，就溢出了。

再来看负数区间，同样考虑倒数第二位，如果本次消费前res < -214748364成立，无论此次消费到的个位数n为多少都溢出了；另一种情况，考虑最后一位，如果本次消费前res = -214748364，那本次消费时n值只要小于-8，就溢出了。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int reverse(int n) {
    // 反转结果初始值
    int res = 0;
    while (n != 0) {
        // 生产：获取个位数
        int x = n % 10;
        // 溢出边界
        if ((res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && x > Integer.MAX_VALUE % 10))
                || (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && x < Integer.MIN_VALUE % 10))) {
            return 0;
        }
        // 消费：加到反转结果后面
        res = res * 10 + x;
        n /= 10;
    }
    return res;
}