【leetcode刷题】T21-132模式
Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:
Input: [, , , ]
Output: False
Explanation: There is no pattern in the sequence.
Example 2:
Input: [, , , ]
Output: True
Explanation: There is a pattern in the sequence: [, , ].
【中文题目】
给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例1:
输入: [, , , ]
输出: False
解释: 序列中不存在模式的子序列。
示例 2:
输入: [, , , ]
输出: True
解释: 序列中有 个模式的子序列： [, , ].
【思路】
（插曲：最开始拿到这题，我想这个不难呀，直接判断是否满足条件nums[i-1] < nums[i+1] < nums[i]，当然有问题，因为题目中的i，j，k只有大小关系，并没有说连续）
拿到题目，首先考虑暴力破解：对于某个数num，遍历其左边区间得到最小值min0，遍历其右边区间得到小于num的最大值max0，判断是否满足条件：min0 < max0 < num。时间复杂度为O(n^2)
有时间复杂度更低的方法吗？
我最开始想的是，上述方法的min0可以不用循环遍历而直接使用变量来更新当前最小值，但是寻找右边区间的max0却没有技巧，只能遍历。这样时间复杂度并没有降低。
看了网友分享后，恍然大悟。我可以用变量存储右边区间的max0，即第二大的数，从右往左遍历，只要找到一个数小于max0，肯定满足条件。那么如何找到第二大的数呢？使用栈！栈里存的可能第二大的数：只要某个数小于max0，满足条件；只要某个数大于栈顶元素，那么max0更新为栈顶元素，栈顶元素弹出，循环判断后将该数压入栈；只要某个数小于栈顶元素，却大于max0，压入栈。（这样，栈里保存的是可能成为第二大的数，并且从栈顶到栈底元素值由小到大）
【代码】
python版本
class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) < :
return False
# 永远保存右边第二大的数
second = -sys.maxsize
stack = []
for n in nums[::-1]:
if n < second:
return True
else:
while(len(stack) > and n > stack[-1]):
second = stack.pop()
stack.append(n)
return False
C++版本
class Solution {
public:
bool find132pattern(vector<int>& nums) {
if(nums.size() < )
return false;
// 永远保存右边第二大的数
int second = INT_MIN;
stack<int> ls;
for(int i=nums.size()-1; i >= ; i--){
if(nums[i] < second)
return true;
else{
while(ls.size() > && nums[i] > ls.top()){
second = ls.top();
ls.pop();
}
ls.push(nums[i]);
}
}
return false;
}
};腾讯云开发者
