मान लीजिए हम एक अनंत संख्या रेखा पर विचार कर रहे हैं, जहां i-वें स्टोन की स्थिति सरणी stones द्वारा दी गई है। एक स्टोन एक एंडपॉइंट स्टोन है यदि उसकी स्थिति सबसे छोटी या सबसे बड़ी है। प्रत्येक चाल में, हम एक एंडपॉइंट स्टोन को उठाते हैं और उसे एक खाली स्थान पर ले जाते हैं ताकि वह अब एंडपॉइंट स्टोन न रहे।
यदि स्टोन्स [1,2,5] पर हैं, तो हम स्थिति 5 पर एंडपॉइंट स्टोन को नहीं ले जा सकते, क्योंकि इसे किसी भी स्थान (जैसे 0 या 3) पर ले जाने से वह अभी भी एंडपॉइंट स्टोन ही रहेगा।
यह खेल तब रुकता है जब हम कोई और चाल नहीं चल सकते, यानी स्टोन्स लगातार स्थितियों में होते हैं। हमें न्यूनतम और अधिकतम चालों की संख्या ज्ञात करनी है जो हम खेल सकते हैं। उत्तर को जोड़ी [min_moves, max_moves] के रूप में दें।
उदाहरण के लिए, इनपुट [7,3,9] के लिए परिणाम [1,3] होगा।
समाधान दृष्टिकोण
- सरणी को सॉर्ट करें।
- **अधिकतम चालें (max_moves):**
max(a[n-2] - a[0], a[n-1] - a[1]) - (n - 2)
यह दोनों छोरों से स्टोन्स को अंदर लाने की सबसे खराब स्थिति दर्शाता है। - **न्यूनतम चालें (min_moves):**
स्लाइडिंग विंडो का उपयोग करके उस विंडो को खोजें जिसमें सबसे अधिक स्टोन्स पहले से ही लगातार हों।
विशेष मामला: यदिn-1स्टोन्स लगातार हैं और केवल एक गैप है (जैसे[1,2,3,5]), तो न्यूनतम चालें 2 होंगी, 1 नहीं।
उदाहरण (C++ कोड)
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++)
cout << v[i] << ", ";
cout << "]" << endl;
}
class Solution {
public:
vector<int> numMovesStonesII(vector<int>& stones) {
sort(stones.begin(), stones.end());
int n = stones.size();
// अधिकतम चालें
int maxMoves = max(stones[n-2] - stones[0], stones[n-1] - stones[1]) - (n - 2);
// न्यूनतम चालें - स्लाइडिंग विंडो
int minMoves = n;
int j = 0;
for (int i = 0; i < n; i++) {
while (j + 1 < n && stones[j+1] - stones[i] < n)
j++;
int count = j - i + 1;
if (count == n - 1 && stones[j] - stones[i] == n - 2)
minMoves = min(minMoves, 2);
else
minMoves = min(minMoves, n - count);
}
return {minMoves, maxMoves};
}
};
int main() {
Solution ob;
vector<int> v1 = {7, 3, 9};
print_vector(ob.numMovesStonesII(v1));
return 0;
} इनपुट
[7,3,9]
आउटपुट
[1, 3]
