समस्या विवरण
मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें जांचना है कि क्या (i, j, k) जैसे ट्रिपलेट्स मौजूद हैं जहां i < j < k और nums[i] < nums[k] < nums[j]।
उदाहरण के लिए, यदि इनपुट है nums = [2, 12, 1, 4, 4], तो आउटपुट True होगा, क्योंकि [2, 12, 4] मानदंड से मेल खाता है क्योंकि 2 < 4 < 12।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- n := nums का आकार
- आकार n का एक ऐरे left परिभाषित करें
- left[0] := nums[0]
- i := 1 से n-1 तक: left[i] := min(nums[i], left[i-1])
- एक स्टैक st परिभाषित करें
- i := n-1 से 1 तक (घटते क्रम में):
- x := left[i-1]
- जब तक st खाली नहीं है और st का शीर्ष ≤ x: st से पॉप करें
- यदि st खाली नहीं है और x < nums[i] और nums[i] > st का शीर्ष, तो true वापस करें
- nums[i] को st में पुश करें
- false वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int>& nums) {
int n = nums.size();
vector<int> left(n);
left[0] = nums[0];
for (int i = 1; i < n; i++) {
left[i] = min(nums[i], left[i - 1]);
}
stack<int> st;
for (int i = n - 1; i >= 1; i--) {
int x = left[i - 1];
while (!st.empty() && st.top() <= x)
st.pop();
if (!st.empty() && x < nums[i] && nums[i] > st.top())
return true;
st.push(nums[i]);
}
return false;
}
};
bool solve(vector<int>& nums) {
return (new Solution())->solve(nums);
}
int main() {
vector<int> v = {2, 12, 1, 4, 4};
cout << solve(v);
}
इनपुट
{2, 12, 1, 4, 4}
आउटपुट
1