66. 加一

转载自Leet Code

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0之外，这个整数不会以零开头。

示例 1: >输入: [1,2,3] >输出:[1,2,4] >解释: 输入数组表示数字 123。

示例 2: >输入: [4,3,2,1] >输出: [4,3,2,2] >解释: 输入数组表示数字 4321。

提示：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

---

我的代码

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}

class MySolution 
{
    public int[] plusOne(int[] digits) 
    {
    	Stack<Integer> stack = new Stack();
    	int carry = 1;
    	
    	for(int i=digits.length-1; i>=0; i--)
    	{
            stack.push((digits[i]+carry)%10);
            carry = (digits[i]+carry)/10;
    	}
    	if (carry!=0) stack.add(carry);
    	
    	int []ans = new int[stack.size()];
    	
    	for(int i=0; i<ans.length; i++)
            ans[i]=stack.pop();
    	
    	return ans;
    }
}