मान लीजिए हमारे पास nums नामक पूर्णांकों की एक सूची है, हमें जांचना है कि क्या हम सूची को दो उप-सूचियों (गैर-खाली) में विभाजित कर सकते हैं जैसे कि बाएं भाग में हर संख्या दाएं भाग में हर संख्या से सख्ती से कम हो।
उदाहरण के लिए, यदि इनपुट [6, 4, 3, 8, 10] है, तो आउटपुट true होगा, क्योंकि बाएं = [6, 4, 3] और दाएं = [8, 10]।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
n := nums का आकार- आकार
nकी एक सरणीrightपरिभाषित करें - आकार
nकी एक सरणीleftपरिभाषित करें left[0] := nums[0]right का अंतिम तत्व := nums का अंतिम तत्वi := 1सेn-1तक लूप चलाएं:left[i] := max(left[i-1], nums[i])
i := n-2से0तक लूप चलाएं:right[i] := min(right[i+1], nums[i])
i := 0सेn-2तक लूप चलाएं:- यदि
left[i] < right[i+1], तोtrueलौटाएं
- यदि
falseलौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& nums) {
int n = nums.size();
vector<int> right(n);
vector<int> left(n);
left[0] = nums[0];
right.back() = nums.back();
for (int i = 1; i < n; i++) {
left[i] = max(left[i-1], nums[i]);
}
for (int i = n-2; i >= 0; i--) {
right[i] = min(right[i+1], nums[i]);
}
for (int i = 0; i < n-1; i++) {
if (left[i] < right[i+1])
return true;
}
return false;
}
};
int main() {
Solution ob;
vector<int> v = {6, 4, 3, 8, 10};
cout << (ob.solve(v));
return 0;
}
इनपुट
{6, 4, 3, 8, 10}
आउटपुट
1