leetcode456 132 Pattern
给定数组，找到 i < j < k i < j < k i<j<k，使得 n u m s [ i ] < n u m s [ k ] < n u m s [ j ] nums[i] < nums[k] < nums[j] nums[i]<nums[k]<nums[j]
最开始肯定想着三重循环，时间复杂度 O ( n 3 ) O(n^3) O(n3)
接着是二重循环
先找到一组 i < j i <j i<j，使得 n u m s [ i ] < n u m s [ j ] nums[i] < nums[j] nums[i]<nums[j]，接着在后面找能放在中间的 k k k
其中 n u m s [ i ] nums[i] nums[i]只要存储左边最小，因为他比其他的更有潜力成为答案
class Solution {
public:bool find132pattern(vector<int>& nums) {int n = nums.size();if(n < 3)return false;bool flag = true;int min_i = nums[0];for(int j = 1; j + 1 < n; ++j){if(nums[j] < min_i){min_i = nums[j];continue;}for(int k = j + 1; k < n; ++k){if(min_i < nums[k] && nums[k] < nums[j]){return true;}}}return false;}
};
然后发现还是超时
所以要一个循环
考虑从右往左遍历
维护一个单调递减栈
当前元素大于栈顶元素时出栈，出栈的最后一个元素作为 n u m s [ k ] nums[k] nums[k]
这样的话相当于先找到了 n u m s [ k ] < n u m s [ j ] nums[k] < nums[j] nums[k]<nums[j]
之后只要找 n u m s [ i ] nums[i] nums[i]
class Solution {
public:bool find132pattern(vector<int>& nums) {if(nums.size() < 3)return false;int max_third = 0x80000000;stack<int> st;for(int i = nums.size() - 1; i >= 0; --i){if(nums[i] < max_third)return true;while(!st.empty() && nums[i] > st.top()){max_third = st.top();st.pop();}st.push(nums[i]);}return false;}
};