题解 | 132序列

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;
    }
}