Mono-increasing stack and reverse order travel (Not Work)

Notes:

  • We attempt to remove the most large numbers in the left,
  • first, we use the right n numbers to meet the requirements, which is num.length - k
  • and then, using a monotonic increasing stack to keep the result as samller as we can.

(A monotonic increasing stack will remove larger elements before pushing.)

Also note that: the result’s length is not actually equal num.length - k, it’s less than or equal num.length - k, like num = “10200”, k = 1. Which means the result in stack could be longer than the required or leading ‘0’.

We failed at:

  • The result is an empty string, that the “0” should be returned. num = “10”, k = 2
  • num = “112”, k = 1
class Solution {
public:
	string removeKdigits(string num, int k) {
		if (num.size() <= k) {
			return "0";
		}
		// A monotonic increasing stack will remove larger elements before pushing.
		stack<char> mst;
		int n = num.size() - k;
		string r;
		for (int i = num.size() - 1; i >= 0; i--) {
			while (mst.size() >= n && mst.top() > num[i]) {
				mst.pop();
			}
			mst.push(num[i]);
		}

		// Pop surplus and the leading '0'
		while (mst.size() > n || (!mst.empty() && mst.top() == '0')) {
			mst.pop();
		}

		while (!mst.empty()) {
			r.push_back(mst.top());
			mst.pop();
		}
		return r.size() > 0 ? r : "0";
	}
};

Mono-increasing stack and normal order travel

We are not focus on keep n - k numbers from right to left, but focus on remove k numbers from left to right.

A more detail explanation to see: https://leetcode.com/problems/remove-k-digits/discuss/1779458/C%2B%2B-oror-Easy-To-Understand-oror-Stack-oror-Short-and-Simple

class Solution {
public:
	string removeKdigits(string num, int k) {
		if (num.size() <= k) {
			return "0";
		}
		// A monotonic increasing stack will remove bigger elements before pushing.
		stack<char> mst;
		int n = num.size() - k;
		string r;

		mst.push(num[0]);
		for (int i = 1; i < num.size(); i++) {
			while (k && !mst.empty() && mst.top() > num[i]) {
				mst.pop();
				k--;
			}

			// the leading zero
			if (mst.size() == 1 && mst.top() == '0') {
				mst.pop();
			}

			mst.push(num[i]);
		}
		while (k && !mst.empty()) {
			k--;
			mst.pop();
		}

		while (!mst.empty()) {
			r.push_back(mst.top());
			mst.pop();
		}
		reverse(r.begin(), r.end());
		return r.size() > 0 ? r : "0";
	}
};