给定一个长度为 n 的整数数组 nums ，请问其中是否存在满足 132 排列的子序列。
132排列的子序列指数组中存在 
满足 %20%5C)
，且 
数据范围： 
，数组中的数满足 
[编程题]132序列
public boolean find132Subseq (ArrayList<Integer> arr) {
// write code here
Integer[] nums = arr.toArray(new Integer[0]);
int min = nums[0];
int max = nums[1]>nums[0]?nums[1]:nums[0];
for(int i=2;i<nums.length;i++){
if(nums[i]>min&&nums[i]<max){
return true;
} else if(nums[i]>min){
max=Math.max(max,nums[i]);
} else if(nums[i]<min){
min=Math.min(min,nums[i]);
max=min;
}
}
return false;
}
发表于 2022-06-30 17:44:05
回复(3)
import java.util.*;
/**
* NC384 132序列
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return bool布尔型
*/
public boolean find132Subseq (ArrayList<Integer> nums) {
// return solution1(nums);
// return solution2(nums);
// return solution3(nums);
// return solution4(nums);
return solution44(nums);
// return solution5(nums);
}
/**
* 枚举j: 二分 -> 超时!
*
* i<j<k
* ... i ... j ... k ...
* ... 1 ... 3 ... 2 ...
*
* nums[i]<nums[k] && nums[k]<nums[j]
* => nums[i]<nums[k]<nums[j]
*
* @param nums
* @return
*/
private boolean solution1(ArrayList<Integer> nums){
int n = nums.size();
if(n < 3){
return false;
}
// 左边比nums[j]小的所有数的最小值 默认满足条件nums[i]<nums[j]
int[] leftMin = new int[n];
// 右边比nums[j]小的所有数的最大值 默认满足条件nums[k]<nums[j]
int[] rightMax = new int[n];
// init
leftMin[0] = Integer.MAX_VALUE;
rightMax[n-1] = Integer.MAX_VALUE;
// nums[i]<nums[j]
int min = nums.get(0);
int num;
for(int j=1; j<n; j++){
num = nums.get(j);
if(min < num){
leftMin[j] = min;
}else{
leftMin[j] = Integer.MAX_VALUE;
min = num;
}
}
int max = nums.get(n-1);
LinkedList<Integer> list = new LinkedList<>();
list.add(nums.get(n-1));
// 枚举j
for(int j=n-2; j>=0; j--){
num = nums.get(j);
if(num > max){
list.add(num);
rightMax[j] = max;
max = num;
}
// 二分
else{
int left = 0;
int right = list.size()-1;
int mid,pos;
while(left <= right){
mid = left+(right-left)/2;
// left最终指向list中第一个大于等于num的位置
if(list.get(mid) < num){
left = mid+1;
}else{
right = mid-1;
}
}
pos = left;
list.add(pos, num);
// nums[k]<nums[j]
if(pos == 0){
rightMax[j] = Integer.MAX_VALUE;
}else{
rightMax[j] = list.get(pos-1);
}
}
if(leftMin[j]==Integer.MAX_VALUE || rightMax[j]==Integer.MAX_VALUE){
continue;
}
// nums[i]<nums[k] => 根据定义可推: nums[i]<nums[k]<nums[j]
if(leftMin[j] < rightMax[j]){
return true;
}
}
return false;
}
/**
* 枚举j: TreeMap(优化)[红黑树]
*
* i<j<k
* ... i ... j ... k ...
* ... 1 ... 3 ... 2 ...
*
* nums[i]<nums[k] && nums[k]<nums[j]
* => nums[i]<nums[k]<nums[j]
*
* @param nums
* @return
*/
private boolean solution2(ArrayList<Integer> nums){
int n = nums.size();
if(n < 3){
return false;
}
// 左边比nums.get(i)小的所有数的最小值 默认满足条件nums[i]<nums[j]
int[] leftMin = new int[n];
// 右边比nums.get(i)小的所有数的最大值 默认满足条件nums[k]<nums[j]
int[] rightMax = new int[n];
// init
leftMin[0] = Integer.MAX_VALUE;
rightMax[n-1] = Integer.MAX_VALUE;
// nums[i]<nums[j]
int min = nums.get(0);
int num;
for(int j=1; j<n; j++){
num = nums.get(j);
if(min < num){
leftMin[j] = min;
}else{
leftMin[j] = Integer.MAX_VALUE;
min = num;
}
}
// 右侧元素 降序
TreeMap<Integer, Integer> rightAll = new TreeMap<>((o1, o2) -> (o2 - o1));
rightAll.put(nums.get(n-1), rightAll.getOrDefault(nums.get(n-1), 0)+1);
Integer next;
// 枚举j
for(int j=n-2; j>=0; j--){
num = nums.get(j);
// nums[k]<nums[j]
// 下一个数(小于等于num-1的所有数的最大值) -> 右边比num小的所有数的最大值
next = rightAll.ceilingKey(num-1);
if(next == null){
rightMax[j] = Integer.MAX_VALUE;
}else{
rightMax[j] = next;
}
rightAll.put(num, rightAll.getOrDefault(num, 0)+1);
if(leftMin[j]==Integer.MAX_VALUE || rightMax[j]==Integer.MAX_VALUE){
continue;
}
// nums[i]<nums[k] => 根据定义可推: nums[i]<nums[k]<nums[j]
if(leftMin[j] < rightMax[j]){
return true;
}
}
return false;
}
/**
* 枚举j: TreeMap(优化)[红黑树]{从左往右遍历}
*
* i<j<k
* ... i ... j ... k ...
* ... 1 ... 3 ... 2 ...
*
* nums[i]<nums[k] && nums[k]<nums[j]
* => nums[i]<nums[k]<nums[j]
*
* @param nums
* @return
*/
private boolean solution3(ArrayList<Integer> nums){
int n = nums.size();
if(n < 3){
return false;
}
// 左侧最小值 nums[i]
int leftMin = nums.get(0);
// 右侧所有元素 升序 nums[k]
TreeMap<Integer, Integer> rightAll = new TreeMap<>();
for(int k=2; k<n; ++k) {
rightAll.put(nums.get(k), rightAll.getOrDefault(nums.get(k), 0)+1);
}
// 枚举j
for(int j=1; j<n-1; j++) {
// nums[i]<nums[j]
if(leftMin < nums.get(j)){
// 下一个数(当前元素右边大于等于leftMin+1的所有数的最小值) nums[i]<nums[k]
Integer next = rightAll.ceilingKey(leftMin+1);
// nums[k]<nums[j] => 可推: nums[i]<nums[k]<nums[j]
if(next!=null && next<nums.get(j)){
return true;
}
}
leftMin = Math.min(leftMin, nums.get(j));
// 右移 -> 移除
rightAll.put(nums.get(j+1), rightAll.get(nums.get(j+1))-1);
if(rightAll.get(nums.get(j+1)) == 0){
rightAll.remove(nums.get(j+1));
}
}
return false;
}
/**
* 枚举i: 单调栈(单调减)
*
* i<j<k
* ... i ... j ... k ...
* ... 1 ... 3 ... 2 ...
*
* nums[i]<nums[k] && nums[k]<nums[j]
* => nums[i]<nums[k]<nums[j]
*
* @param nums
* @return
*/
private boolean solution4(ArrayList<Integer> nums){
int n = nums.size();
if (n < 3) {
return false;
}
Stack<Integer> stack = new Stack<>();
stack.push(nums.get(n-1));
int maxK = Integer.MIN_VALUE;
int num;
for(int i=n-2; i>=0; i--){
num = nums.get(i);
// nums[i]<nums[k]
if(num < maxK){
return true;
}
// nums[k]<nums[j]
while(!stack.isEmpty() && num>stack.peek()){
maxK = stack.pop();
}
// stack.push(num);
// 优化 -> 不会将maxK更新为更大的值(不用入栈)
if(num > maxK){
stack.push(num);
}
}
return false;
}
/**
* 枚举i: 单调栈(单调减)
*
* i<j<k
* ... i ... j ... k ...
* ... 1 ... 3 ... 2 ...
*
* nums[i]<nums[k] && nums[k]<nums[j]
* => nums[i]<nums[k]<nums[j]
*
* @param nums
* @return
*/
private boolean solution44(ArrayList<Integer> nums){
int n = nums.size();
if (n < 3) {
return false;
}
Stack<Integer> stack = new Stack<>();
int maxK = Integer.MIN_VALUE;
int num;
// 枚举i
for(int i=n-1; i>=0; i--){
num = nums.get(i);
// nums[i]<nums[k]
if(num < maxK){
return true;
}
// 单调栈 单调减(从右向左)[可求解当前num右边: 小于num的最大值 或 大于num的最小值] nums[k]<nums[j]
while(!stack.isEmpty() && stack.peek()<num){
// maxK: 当前num右边小于num的最大值
maxK = stack.pop();
}
// stack.push(num);
// 优化
if(num > maxK){
stack.push(num);
}
}
return false;
}
/**
* 枚举k: 单调栈(单调减)+二分(单调栈上二分)
*
* i<j<k
* ... i ... j ... k ...
* ... 1 ... 3 ... 2 ...
*
* nums[i]<nums[k] && nums[k]<nums[j]
* => nums[i]<nums[k]<nums[j]
*
* @param nums
* @return
*/
private boolean solution5(ArrayList<Integer> nums){
int n = nums.size();
if (n < 3) {
return false;
}
// 模拟单调栈(单调减)
List<Integer> candidateI = new ArrayList<>();
candidateI.add(nums.get(0));
// 模拟单调栈(单调减)
List<Integer> candidateJ = new ArrayList<>();
candidateJ.add(nums.get(0));
int num;
for(int k=1; k<n; ++k) {
num = nums.get(k);
// i位置
int idxI = binarySearchFirst(candidateI, num);
// j位置
int idxJ = binarySearchLast(candidateJ, num);
// nums[i]<nums[k] && nums[k]<nums[j]
if(idxI>=0 && idxJ>=0){
// 保证i<j (nums[i]在前 nums[j]在后)
if(idxI <= idxJ){
return true;
}
}
if(num < candidateI.get(candidateI.size()-1)){
candidateI.add(num);
candidateJ.add(num);
}else if(num > candidateJ.get(candidateJ.size()-1)){
int lastI = candidateI.get(candidateI.size()-1);
while(!candidateJ.isEmpty() && num>candidateJ.get(candidateJ.size()-1)){
candidateI.remove(candidateI.size()-1);
candidateJ.remove(candidateJ.size()-1);
}
// 尽量小
candidateI.add(lastI);
candidateJ.add(num);
}
}
return false;
}
/**
* 二分查找最前一个小于target(nums[k])的索引(i位置) -> nums[i]<nums[k] (i索引 尽量往左尽量小)
* @param candidate 单调减
* @param target
* @return
*/
public int binarySearchFirst(List<Integer> candidate, int target) {
int left=0;
int right = candidate.size()-1;
if (candidate.get(right) >= target) {
return -1;
}
int result = -1;
int mid;
while(left <= right){
mid = left+(right-left)/2;
if(candidate.get(mid) >= target){
left = mid+1;
}else{
result = mid;
right = mid-1;
}
}
return result;
}
/**
* 二分查找最后一个大于target(nums[k])的索引(j位置) -> nums[k]<nums[j] (j索引 尽量往右尽量大)
* @param candidate 单调减
* @param target
* @return
*/
public int binarySearchLast(List<Integer> candidate, int target) {
int left = 0;
int right = candidate.size()-1;
if (candidate.get(left) <= target) {
return -1;
}
int result = -1;
int mid;
while(left <= right){
mid = left+(right-left)/2;
if(candidate.get(mid) > target){
result = mid;
left = mid+1;
}else{
right = mid-1;
}
}
return result;
}
}
发表于 2025-02-11 13:38:13
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return bool布尔型
*/
bool find132Subseq(vector<int>& nums) {
// write code here
stack<int> st;
st.push(nums[0]);
for(int i=1;i<nums.size();i++)
{
int ctl=-1;
while(!st.empty()&&(st.top()>nums[i]))
{
if(st.size()>=2)
{
ctl=0;
}
st.pop();
}
if(!st.empty())
{
ctl++;
}
if(ctl==1)
{
return true;
}
st.push(nums[i]);
}
return false;
}
};
发表于 2022-07-01 12:11:06
回复(0)
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return bool布尔型 # class Solution: """ 题目： https://www.nowcoder.com/practice/eae8142169a74ad7884bb5dca3264128?tpId=196&tqId=40515&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 算法： 132序列：i < j < k 且 nums[i] < nums[k] < nums[j]，这里我们借助单调不减栈stack，存储元素的下标，使用flag表示是否存在逆序对 遍历nums： 若栈不空 且 存在逆序对： flag置为True，弹出栈顶 若找到逆序对： 将stack中对应元素与nums[i]相等的下标，全部弹出 若此时stack仍存在元素，说明满足132序列；否则重置flag=False 遍历结束，返回False 复杂度： 时间复杂度：O(n) 空间复杂度：O(n) """ def find132Subseq(self, nums): # write code here n = len(nums) stack, flag = [], False for i in range(n): while stack and nums[stack[-1]] > nums[i]: # 找到逆序对nums[k] < nums[j]，需要再判断是否满足nums[i] < nums[k] flag = True # flag表示是否找到逆序对 stack.pop() if flag: while stack and nums[stack[-1]] == nums[i]: # 比如[1, 2, 1]不合符条件 stack.pop() if stack: # [2, 3, 1] return True else: # 比如[3, 2, 1]，属于无效逆序对，重置flag = False flag = False stack.append(i) return False if __name__ == "__main__": sol = Solution() # nums = [1, 2, 3, 2, 1] # nums = [82, 78, 12, 42, 65] # nums = [2, 2, 2, 2] nums = [1, 2, 1] res = sol.find132Subseq(nums) print res
发表于 2022-06-27 14:11:57
回复(0)
问题信息
难度：
4条回答
22收藏
3916浏览
通过挑战的用户
查看代码-
2022-09-10 21:50:48
-
2022-09-08 16:53:37
-
2022-09-04 16:04:42
-
2022-09-04 16:04:03 -
2022-09-04 15:16:33
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
