leetcode 334. Increasing Triplet Subsequence

逃离我推掉我的手 2022-08-20 10:13 15阅读 0赞

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.  
  
  
Formally the function should:  
Return true if there exists i, j, k   
such that arr\[i\] < arr\[j\] < arr\[k\] given 0 ≤ i < j < k ≤ n-1 else return false.  
Your algorithm should run in O(n) time complexity and O(1) space complexity.  
  
  
Examples:  
Given \[1, 2, 3, 4, 5\],  
return true.  
  
  
Given \[5, 4, 3, 2, 1\],

return false.

#include "stdafx.h"
    #include<vector>
    #include<iostream>
    using namespace std;
    
    class Solution {
    public:
    	bool increasingTriplet(vector<int>& nums)
    	{
    		if (nums.size() < 3)
    			return false;
    		vector<vector<int>>gtthan;
    		for (int i = 0; i < nums.size(); i++)
    		{
    			vector<int>temp;
    			gtthan.push_back(temp);
    			for (int j = i + 1; j < nums.size(); j++)
    			{
    				if (nums[j]>nums[i])
    					gtthan[i].push_back(j);
    			}
    		}
    		int num1, num2, num3;
    		for (int i = 0; i < nums.size() - 2; i++)
    		{
    			num1 = nums[i];
    			for (int j = 0; j < gtthan[i].size(); j++)
    			{
    				num2 = nums[gtthan[i][j]];
    				for (int k = 0; k < gtthan[gtthan[i][j]].size(); k++)
    				{
    					//if (gtthan[gtthan[i][j]].size()>0)
    					return true;
    				}
    			}
    		}
    		return false;
    	}
    };
    
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int a[5] = { 1, 2, -10, -8, -7};
    	vector<int>nums(a, a + 5);
    	Solution sl;
    	cout<<sl.increasingTriplet(nums);
    	system("pause");
    	return 0;
    }

acceped