Priority Queue | Max Heap | Clean Code | Easy Explaination |
Intuition\nIf you reached here it\'s for sure you not able to get to the solution in the first place dont worry I did the same mistake. \n\nJust read the questi
# Intuition\nIf you reached here it\'s for sure you not able to get to the solution in the first place dont worry I did the same mistake. \n\nJust read the question nicely, It says every time you have to pick the stones with largest weight, so for sure you might have sorted the Array and applied a greedy approach,but you\'ll have to perform sort operation everytime you perform a operation. \n\nSo priority queue uses a Data structure called Max heap for the implemenation where the top node is always the maximum and we can get it in 0(1) time.\n\nYou can see the code we just pop two top stones with heigest weight and put a stone again in it.\n\n# Approach\nSimple thinking, Heap Data structure greedy.\n\n# Complexity\n- Time complexity:\nCreation of priority-0(nlogn)\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int lastStoneWeight(vector<int>& stones) {\n        int n = stones.size();\n        priority_queue<int> pq;\n        for(int i=0;i<n;i++) pq.push(stones[i]);\n        while(pq.size()>=2)\n        {\n           int x = pq.top(); pq.pop();\n           int y = pq.top(); pq.pop();\n           if(x!=y) pq.push(abs(x-y));\n\n        }if(pq.size()==0) return 0;\n        return pq.top();\n\n\n    }\n};\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++']