Số nhỏ nhất sau khi xóa n chữ số trong JavaScript

Vấn đề

Chúng tôi bắt buộc phải viết một hàm JavaScript có hai số, hãy gọi chúng là m và n lần lượt là đối số đầu tiên và đối số thứ hai.

Nhiệm vụ của hàm chúng ta là xóa n chữ số khỏi số m để số m là số nhỏ nhất có thể sau khi xóa n chữ số. Và cuối cùng, hàm sẽ trả về số m sau khi loại bỏ các chữ số.

Ví dụ:nếu đầu vào của hàm là -

const m = '45456757';
const n = 3;

Sau đó, đầu ra phải là -

const output = '44557';

Giải thích đầu ra:

Chúng tôi đã loại bỏ chữ số 5, 6 và 7 để có được số nhỏ nhất có thể.

Ví dụ

Mã cho điều này sẽ là -

const m = '45456757';
const n = 3;
const removeDigits = (m, n, stack = []) => {
   let arr = m.split('').map(Number);
   for(let el of arr){
      while (n && stack.length && el < stack[stack.length - 1]){
         stack.pop();
         --n;
      };
      stack.push(el);
   };
   let begin = stack.findIndex(el => el > 0);
   let end = stack.length - n;
   return (!stack.length || begin == -1 || begin == end) ? "0" : stack.slice(begin, end).join('').toString();
};
console.log(removeDigits(m, n));

Giải thích mã:

Ở đây, chúng tôi đã sử dụng một thuật toán tham lam bằng cách sử dụng một ngăn xếp để hình thành câu trả lời. Đối với mỗi giá trị el của chuỗi đầu vào num từ trái sang phải, chúng tôi đẩy el vào ngăn xếp sau khi chúng tôi đã xóa tối đa n giá trị từ ngăn xếp lớn hơn el.

Vì các vị trí ngoài cùng bên trái của một số có giá trị hơn các vị trí ngoài cùng bên phải, cách tiếp cận tham lam này đảm bảo các vị trí ngoài cùng bên trái bao gồm các chữ số nhỏ nhất và bất cứ thứ gì còn lại trong ngăn xếp là các chữ số lớn nhất ở bên phải- hầu hết các vị trí.

Sau khi chuỗi đầu vào m đã được xử lý nếu còn lại n chữ số cần loại bỏ thì hãy loại bỏ n chữ số ngoài cùng bên phải, vì n chữ số ngoài cùng bên phải là chữ số lớn nhất.

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

44557