从C ++中的列表中找到三元组nums [i]
假设我们有一个称为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。
例
让我们看下面的实现以更好地理解-
#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