132 Pattern-K6K4.com

原题： https://leetcode.com/problems/132-pattern/description/

题意： 给定整数序列a1, a2, ..., an，132模式是指一组序列 ai, aj, ak 满足 i < j < k and ai < ak < aj。设计算法判断长度为n的整数列表中是否包含132模式。

约定： n < 15000

例子：

例一:
输入: [1, 2, 3, 4]
输出: False
说明: 序列中没有132模式。

例二:
输入: [3, 1, 4, 2]
输出: True
说明: 序列中有一个132模式：[1,4,2]。

例三:
输入: [-1, 3, 2, 0]
输出: True
说明: 序列中有三个132模式：[-1,3,2]，[-1,3,0]和[-1,2,0]。

标签： aj、ak、序列、pattern、例三、面试

猜你感兴趣的圈子：

LeetCode交流圈

星空

2017-08-18 18:30:04 1楼#1层

public class Solution {
    public boolean find132pattern(int[] nums) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int num : nums) {
            tm.put(num, tm.getOrDefault(num, 0) + 1);
        }
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            int cnt = tm.get(num);
            if (cnt > 1) {
                tm.put(num, cnt - 1);
            } else {
                tm.remove(num);
            }
            if (num <= min) {
                min = num;
            } else {
                Integer target = tm.higherKey(min);
                if (target != null && target < num) {
                    return true;
                }
            }
        }
        return false;
    }
}

星空

2017-08-18 18:30:45 2楼#1层

class Solution {
public:
     bool find132pattern(vector<int>& nums) {
        int s3 = INT_MIN;
        stack<int> st;
        for( int i = nums.size()-1; i >= 0; i -- ){
            if( nums[i] < s3 ) return true;
            else while( !st.empty() && nums[i] > st.top() ){ 
              s3 = st.top(); st.pop(); 
            }
            st.push(nums[i]);
        }
        return false;
    }
};

星空

2017-08-18 18:33:20 3楼#1层

class Solution {
    public boolean find132pattern(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) return true;
            }
        }
    }
    return false;
}
}

星空

2017-08-18 18:34:05 4楼#1层

class Solution {
  public boolean find132pattern(int[] nums) {
    for (int n = nums.length, i = n - 1, top = n, third = Integer.MIN_VALUE; i >= 0; i--) {
        if (nums[i] < third) return true;
        while (top < n && nums[i] > nums[top]) third = nums[top++];
        nums[--top] = nums[i];
    }
    
    return false;
}
}

取消

回复

推荐圈子

LeetCode交流圈