最近一网友爆料，在携程研发岗位，工作每天早十晚九，组里强制要求工时10个小时以上，如果不够会被约谈。本来是冲着养老，WLB（Work-Life Balance，工作与生活平衡）来的，结果现在完全名不副实。
对于这种爆料，有不少认证为携程的员工评论该消息属实，看来这个爆料应该是真的了。强制10小时以上，越来越无视劳动法了，估计是受抖音直播的印象，携程现在越来越走下坡路了。
我记得很早的时候出去旅游一直使用的是去哪网，后来2015年的时候被携程收购，后面出去旅游，买票，住酒店等基本上都是在携程上下单。由于最近几年受抖音直播的影响，发现那些直播的更便宜，所以一直就没怎么使用携程了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第402题：移掉 K 位数字，难度是中等。
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例1：
输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例2：
输入：num = "10200", k = 1 输出："200" 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
1 <= k <= num.length <= 10^5
num 仅由若干位数字（0 - 9）组成
除了 0 本身之外，num 不含任何前导零
问题分析
这题说的是在一个非负的整数中移除 k 个数字，使剩下的整数最小。在解这题之前我们来找一下规律。
如果数字都是递增的，比如1234579，只有从后往前移除才会使剩下的数字最小。
如果数字不全是递增的，比如15426789，如果移除一个数字，只能移除 5 ，如果移除两个数字，只能移除 5 和 4 ，如果移除 3 个以上的数字，在移除 5 和 4 之后，只能从后往前移除了。
所以这题我们找到规律了，可以使用单调栈来解决，从左往右遍历每一个数字，如果当前数字比栈顶元素大（或者等于），就让当前数字入栈。如果当前数字比栈顶元素小，栈顶元素出栈，然后继续和新的栈顶元素比较。
如果删除的数字个数不到 k 个，只能从后往前删除了，直到删除 k 个为止。
JAVA：
public String removeKdigits(String num, int k) { Deque dq = new LinkedList<>();// 双端队列 for (char ch : num.toCharArray()) { // 队尾元素大于当前元素，队尾元素要出队 while (k > 0 && !dq.isEmpty() && dq.peekLast() > ch) { dq.pollLast(); k--; } dq.offerLast(ch); } while (k-- > 0)// 继续移除，直到移除 k 个为止 dq.pollLast(); while (!dq.isEmpty() && dq.peekFirst() == '0')// 移除前导 0 dq.pollFirst(); // 把队列中的字符转成字符串 StringBuilder sb = new StringBuilder(); while (!dq.isEmpty()) sb.append(dq.pollFirst()); return sb.length() == 0 ? "0" : sb.toString(); }C++：
public: string removeKdigits(string num, int k) { deque
dq;// 双端队列 for (constchar &ch: num) { // 队尾元素大于当前元素，队尾元素要出队 while (k > 0 && !dq.empty() && dq.back() > ch) { dq.pop_back(); k--; } dq.push_back(ch); } while (k-- > 0)// 继续移除，直到移除 k 个为止 dq.pop_back(); while (!dq.empty() && dq.front() == '0')// 移除前导 0 dq.pop_front(); // 把队列中的字符转成字符串 string ans; while (!dq.empty()) { ans += dq.front(); dq.pop_front(); } return ans.empty() ? "0" : ans; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。
热门跟贴