Heap ?
Monotonic Stack is the optimal approach but let\'s see how can we solve using heap. \n\n# Intuition\n Describe your first thoughts on how to solve this problem.
Monotonic Stack is the optimal approach but let\'s see how can we solve using heap. \n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need smallest element first but that element should be within reach as only k removals are allowed. \n\n**s = "98721" k = 3**\n- we can\'t have result starting from 1 even though it\'s the smallest. \n- But we can have result starting from 2 by removing "987".(res = "21")\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- We make use of min heap here to get the smallest element first with it\'s index. <element, index>\n- if the smallest element is not within reach (i.e we need to remove more than k elements), then we can simply pop it and get the next smallest element!..\n\n- we have to make sure to not add zeros in empty res and remove older index element.\n\n# Complexity\n- Time complexity: O (N LOG N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O (N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n//APPROACH 1 : my intuition:::  O(NlogN)\n\n    string removeKdigits(string num, int k) {\n        int n = num.size();\n\n        priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > minHeap; \n\n        for (int i = 0; i < n; i++){\n            minHeap.push({num[i]-\'0\', i});\n        }\n\n        string res = "";\n\n        for (int i = 0; i < n; i++){\n            if (res == "" && num[i] == \'0\') \n                continue;\n\n            if (k > 0){ //find smallest element that is possible to be inserted into the answer!\n                queue<pair<int,int>>temp;\n\n                while(!minHeap.empty()){ //only keep valid indices\n\n                    auto top = minHeap.top();\n                    minHeap.pop();\n\n                    if (top.second >= i){\n                        //check if we can use it\n                        if (top.second - i <= k){\n                            k -= (top.second-i);\n\n                            if ((res == "" && num[top.second] == \'0\') == false)\n                                res += num[top.second];\n\n                            i = top.second;//i++ on for loop to go to the next index\n                            break;\n                        }\n                        //create backup\n                        else  temp.push(top);\n                    }\n                }\n                //restore from backup\n                while (!temp.empty()){\n                    minHeap.push(temp.front());\n                    temp.pop();\n                }\n            }\n            else { //k == 0, simply add to the result\n                res += num[i];\n            }\n        }\n        while(k-- && res != ""){ //res is already sorted we\'ll remove from back to get the smallest possible result\n            res.pop_back();\n        }\n        return res.size() == 0 ? "0" : res;\n    }\n```
['Queue', 'Heap (Priority Queue)', 'Monotonic Stack', 'C++']