题解
题意：给定数组a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。 给定数组nums[]，判断是否有132模式 题解：此题主要是找到一个下标最大的中间值，下标最小的最小值，和下标中间的最大值。 下标最小的最小值最好找，就是从前往后遍历一遍数组，第j个位置的最小值就是以j为末尾元素的前缀数组的最小值， 因此首先用一个min数组来记录到第j个数字之前出现的最小值 下标最大的中间值则可以通过维护一个单调递减栈来实现。因为要求下标最大，因此我们可以考虑从后往前遍历数组。 每次遍历的时候需要判断栈顶元素是否小于等于前缀最小值（随着下标的减小，前缀最小值可能会增大），如果是，则栈顶将无效，将其pop出来 否则栈顶元素有效，如果此时栈顶元素小于第i个元素，即nums[j] > s.peek()&&s.peek()>min[j]，说明已经找到了132模式。 因为栈顶元素是从后往前存储的，对应元素的下标一定不会小于j，此外，前缀最小值是下标i之前的最小值，那么前缀最小值不等于nums[j]的下标也一定是小于j 实现
public boolean find132pattern(int[] nums) {
boolean flag = false;
Stack<Integer> s = new Stack<Integer>();
int n = nums.length;
if(n < 3) return false;
final int N = 15003;
int []min = new int[N];
min[0] = nums[0];
for(int i = 1;i < n;i++)
min[i] = Math.min(nums[i],min[i-1]);
for(int j = n-1;j >= 0;j--){
while(!s.empty() && (s.peek() <= min[j])){
s.pop();
}
if(s.empty() || s.peek() >= nums[j]){
s.push(nums[j]);
}
if(s.peek() > min[j] && s.peek() < nums[j]) return true;
}
return false;
}
题目
