网友爆料上海携程211硕士强制10小时被约谈。。

最近一网友爆料，在携程研发岗位，工作每天早十晚九，组里强制要求工时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多题，对算法题有自己独特的解题思路和解题技巧。