สมมติว่าเรามีจำนวนเต็มที่ไม่เป็นลบซึ่งแสดงเป็นสตริง เราต้องลบหลัก k ออกจากตัวเลขเพื่อให้ตัวเลขใหม่มีค่าน้อยที่สุด ดังนั้นหากอินพุตเป็น “1432219” และ k =3 ผลลัพธ์จะเป็น “1219”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนด stack st สร้าง string ว่าง ret
-
n :=ขนาดของ num
-
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
-
ในขณะที่ k ไม่ใช่ศูนย์และ stack ไม่ว่างและด้านบนของ stack> num[i]
-
ลบออกจากสแต็กและลด k ลง 1
-
-
ใส่ num[i] ลงใน st
-
-
ในขณะที่ k ไม่ใช่ 0 ให้ลบองค์ประกอบออกจากสแต็ก
-
ในขณะที่สแต็กไม่ว่างเปล่า
-
ret :=ret + ด้านบนของ stack ลบองค์ประกอบออกจาก stack
-
-
ตอนนี้กลับสตริง ret
-
ans :=สตริงว่าง และ i :=0
-
ในขณะที่ i <ขนาดของ ret และ ret[i] ไม่ใช่ '0'
-
เพิ่มขึ้น 1
-
-
สำหรับฉัน <ขนาดของ ret
-
ans :=ans + ret[i]
-
-
ret :=ans
-
คืนค่า “0” หากขนาดของ ret เป็น 0 มิฉะนั้น ret
ตัวอย่าง (C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution {
public:
string removeKdigits(string num, int k) {
stack st;
string ret = "";
int n = num.size();
for(int i = 0; i < n; i++){
while(k && !st.empty() && st.top() > num[i]){
st.pop();
k--;
}
st.push(num[i]);
}
while(k--)st.pop();
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
string ans = "";
int i = 0;
while(i <ret.size() && ret[i] == '0')i++;
for(; i < ret.size(); i++)ans += ret[i];
ret = ans;
return ret.size() == 0? "0" : ret;
}
}; อินพุต
"1432219" 3
ผลลัพธ์
"1219"
