How to get the maximum number after erasing n digits from the number [closed]

by

The solution to this question has been beautifully answered here.
Only difference is you have to keep the stack sorted decreasingly.

# process digits from left to right
for each digit from left to right
  if digit <= top of the stack
    push(digit)
    continue
  while (digit > top of the stack) and (we have enough digits to reach n-k digits)
    pop()
  push(digit)
pop extra digits

9511145
push(9) => 9
push(5) because 5 <= 9 => 95
push(1) because 1 <= 5 => 951
push(1) because 1 <= 1 => 9511
push(1) because 1 <= 1 => 95111
pop() because 4 > 1 and we can still end up with 4 digits => 9511
pop() because 4 > 1 and we can still end up with 4 digits => 951
pop() because 4 > 1 and we can still end up with 4 digits => 95
push(4) because 4 <= 5 => 954
push(5) because we need to have 4 digits at least => 9545

NOTE: upvote original answer.

More Related Contents:

  1. LRU cache design
  2. what is the difference between set and unordered_set in C++?
  3. TMP: how to generalize a Cartesian Product of Vectors?
  4. Why would anyone use set instead of unordered_set?
  5. Easiest way of using min priority queue with key update in C++
  6. Order Statistic Tree in C++
  7. Mixing two arrays by alternating elements two by two
  8. Recursive and non-recursive traversal of three degree tree
  9. banker’s algorithm in c++
  10. What is the difference between palindrome permutation and permutation? [closed]
  11. How to replace all occurrences of a character in string?
  12. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  13. How to reverse a singly linked list using only two pointers?
  14. Visual C++ equivalent of GCC’s __attribute__ ((__packed__))
  15. Fast ceiling of an integer division in C / C++
  16. Looking for C++ STL-like vector class but using stack storage
  17. Is there a way to access the underlying container of STL container adaptors?
  18. Search for a struct item in a vector by member data
  19. How to store extremely large numbers?
  20. How to create a trie in c# [closed]
  21. C++ Efficiently Calculating a Running Median [duplicate]
  22. Finding nearest point in an efficient way
  23. Fast n choose k mod p for large n?
  24. Inverting a 4×4 matrix
  25. Print 2-D Array in clockwise expanding spiral from center
  26. std::back_inserter for a std::set?
  27. How to rotate a N x N matrix by 90 degrees? [closed]
  28. How to find Longest Common Substring using C++
  29. Mapping elements in 2D upper triangle and lower triangle to linear structure
  30. Generate N random numbers within a range with a constant sum

Leave a Comment