456. 132模式

我就是我 2022-11-13 00:48 138阅读 0赞

# 456. 132模式 #

给你一个整数数组 `nums` ，数组中共有 `n` 个整数。**132 模式的子序列** 由三个整数 `nums[i]`、`nums[j]` 和 `nums[k]` 组成，并同时满足：`i < j < k` 和 `nums[i] < nums[k] < nums[j]` 。

如果 `nums` 中存在 **132 模式的子序列** ，返回 `true` ；否则，返回 `false` 。

\*\*进阶：\*\*很容易想到时间复杂度为 `O(n^2)` 的解决方案，你可以设计一个时间复杂度为 `O(n logn)` 或 `O(n)` 的解决方案吗？

**示例 1：**

输入：nums = [1,2,3,4]
    输出：false
    解释：序列中不存在 132 模式的子序列。

**示例 2：**

输入：nums = [3,1,4,2]
    输出：true
    解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

**示例 3：**

输入：nums = [-1,3,2,0]
    输出：true
    解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

**提示：**

*  `n == nums.length`
 *  `1 <= n <= 104`
 *   − 1 0 9 -10^\{9\} −109 <= `nums[i]`<=  1 0 9 10^\{9\} 109

# 思路与代码 #

这个方法就是 O(N^2)*O*(*N*2) 的解法，是这个题的暴力解法。

我选择的方法是维护 132模式 中间的那个数字 3，因为 3 在 132 的中间的数字、也是最大的数字。我们的思路是个**贪心**的方法：我们要维护的 1 是 3 左边的**最小的数字；** 2 是 3 右边的比 3 小并且比 1 大的数字。

从左到右遍历一次，遍历的数字是 nums\[j\]*n**u**m\*\*s*\[*j*\] 也就是 132 模式中的 3。根据上面的**贪心**思想分析，我们想让 1 是 3 左边最小的元素，然后使用暴力在 nums\[j+1 … N-1\]*n**u**m\*\*s*\[*j*\+1…*N*−1\] 中找到 132 模式中的 2 就行。

这个思路比较简单，也能 AC。

#include <iostream>
    #include <string>
    #include "stack"
    #include "vector"
    
    using namespace std;
    
    //456. 132模式
    class Solution { 
    
    public:
    	bool find132pattern(vector<int>& nums) { 
    		int numi=nums[0];
    		for (int j=1;j<nums.size();j++){ 
    			int numj = nums[j];
    			for (int k= nums.size() - 1;k>j;k--){ 
    				int numk = nums[k];
    				numj = nums[j];
    				if (numi < numk && numk < numj) { 
    					return true;
    				}
    			}
    			numi = min(numi, numj);
    		}
    		return false;
    	}
    
    
    
    };
    
    int main()
    { 
    	Solution s;
    	vector<int> nums;
    	nums.push_back(1);
    	nums.push_back(2);
    	nums.push_back(4);
    	nums.push_back(3);
    	
    	cout << "find132pattern="<<s.find132pattern(nums) << endl;
    	system("pause");
    }
    
    //执行用时：1144 ms, 在所有 C++ 提交中击败了5.51 %的用户
    //内存消耗：13 MB, 在所有 C++ 提交中击败了94.49 %的用户