C++ O(nlogn) with detailed explanation
Sort it first.\n1. How to get the minimum steps?\n\tWe can transfer this question into a problem like:\n\tFind the longest subsequence of a sorted array with ma
Sort it first.\n1. How to get the minimum steps?\n\tWe can transfer this question into a problem like:\n\tFind the longest subsequence of a sorted array with max difference==n-1;\n\tFor example, [1, 4, 5, 6, 10], the longest subsequence is 4,5,6, we just need to move 1 and 10 close to 4, 5, 6, so we just need n - len: 5-3 = 2 steps.\n\tNotice that 3,4,5,6,10 is a special case, 2 steps too, so if there are n-1 consecutive numbers, add 1 to minimum steps.\n\t\n2. How to find maximum steps?\nSuppose 1, 10, 20, 30, 100;\nif we move100, then;\n1,10,20,29,30\n1,10,20,28,29\n....\n1,2,3,4,5\nif we move 1, then:\n\t\t\t10,11,20,30,100\n\t\t\t11,12,20,30,100\n\t\t\t....\n\t\t\t96,97,98,99,100\n\t\t\t\n\tGOT IT?\n\tWe just need to compute the largest interval not including 1 endpoint.\n\tfor example, in the previous example, \n\tlargest_interval = max(100-10, 30-1);\n\tso slots_betweet_largest_interval = 100-10-1=89\n\tthen we know there are n-3 stones between the largest interval, so the remaining slots are the maximized steps we can move.\n\tthat is 89-(n-3)=89-(5-3)=87\n```\n\tclass Solution {\npublic:\n    vector<int> numMovesStonesII(vector<int>& A) {\n        int n = A.size();\n        int maxcon = 1, start, end, j = 0;\n        int si=0, ei=0;\n        sort(A.begin(), A.end());\n        for(int i = 0; i < n; i++) {\n            start = A[i];\n            end = start+n;\n            while(j<n&&A[j]<end) {\n                j++;\n            }\n            if(j-i>maxcon||(j-i==maxcon&&A[j-1]-A[i]>ei-si)){\n                si=A[i];\n                ei=A[j-1];\n                maxcon=j-i;\n            }\n        }\n        \n        int minimum = n-maxcon;\n        if(maxcon==n-1&&ei-si==maxcon-1) minimum++;\n        if(maxcon==n) minimum=0;\n        int largest_interval = max(A[n-1]-A[1], A[n-2]-A[0])-1;\n        int maximum =  largest_interval-(n-3);\n        return {minimum, maximum};\n    }\n}\n```;
[]