题目
给定一个整数序列:a1, a2, ..., an,一个 132 模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak < aj。设计一个算法,当给定有 n 个数字的序列时,验证这个序列中是否含有 132 模式的子序列。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/132-pattern
代码
public class DayCode {
public static void main(String[] args) {
int[] nums = new int[]{};
boolean ans = new DayCode().find132pattern(nums);
System.out.println(ans);
}
/**
* 题目链接:https://leetcode-cn.com/problems/132-pattern/
* 时间复杂度 O(n)
* 空间复杂度 O(n)
*
* @param nums
* @return
*/
public boolean find132pattern(int[] nums) {
boolean ans = false;
int n = nums.length;
if (n < 3) {
return ans;
}
int[] minArr = new int[n];
minArr[0] = nums[0];
for (int i = 1; i < n; i++) {
minArr[i] = Math.min(minArr[i - 1], nums[i]);
}
Stack<Integer> stack = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
if (nums[i] > minArr[i]) {
while (!stack.isEmpty() && stack.peek() <= minArr[i]) {
stack.pop();
}
if (!stack.isEmpty() && stack.peek() < nums[i]) {
ans = true;
return ans;
}
stack.push(nums[i]);
}
}
return ans;
}
}
复制代码
总结
评论