网站服务器++免费,网络网站租,找公司网站建设,上海做网站待遇给你一个以字符串表示的非负整数 num 和一个整数 k #xff0c;移除这个数中的 k 位数字#xff0c;使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 #xff1a;
输入#xff1a;num 1432219, k 3
输出#xff1a;1219
解…给你一个以字符串表示的非负整数 num 和一个整数 k 移除这个数中的 k 位数字使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1
输入num 1432219, k 3
输出1219
解释移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。示例 2
输入num 10200, k 1
输出200
解释移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。示例 3
输入num 10, k 2
输出0
解释从原数字移除所有的数字剩余为空就是 0 。
1 k num.length 105num 仅由若干位数字0 - 9组成除了 0 本身之外num 不含任何前导零
单调栈
比较a和b的大小是从最高位开始进行比较的。 那么我们也应该是从最高位开始进行删数。所以就是对num进行单调上升栈的维护。 逐个数字入栈当发现当前入栈元素栈顶元素s.top()的时候就s.pop()维护栈的单调递增性。 这样就可以保证结果的最高位最小并以此递增。
当所有元素都进行过栈的处理之后如果结果stack中的元素比要保留的长度要长的话则把栈顶元素pop掉。 在入栈的时候可忽略掉前置0.
string removeKdigits(string num, int k) {stackchar s;for (char i num){while (!s.empty() s.top() i k){s.pop();k--;}if (s.empty() i 0)continue;//跳过前置0s.push(i);}string res;while (!s.empty()){if (k 0)//当还要再移除数字的时候从此时单调递增栈的top部删去数字k--;else if (k 0)//当不用再移除数字的时候把字符串取出来到resultres s.top();s.pop(); }reverse(res.begin(), res.end());//stl中的reverse函数return res ? 0 : res;
}用string实现的单调栈
不用初始化一个栈而是直接用string来实现栈的功能维护单调上升的序列。
class Solution {
public:
string removeKdigits(string num, int k)
{string result;for (int i 0; i num.size(); i){while (result.size() kresult.back() num[i]){result.pop_back();k--;}if (result.size() 0 num[i] 0)continue;resultnum[i];}while (k 0 !result.empty()){result.pop_back();k--;}return result ? 0 : result;
}
};
