Java scan twice O(n)


  • 0
    D
    public class Solution {
        public boolean find132pattern(int[] nums) {
            if (nums == null || nums.length < 3) {
                return false;
            }
            int n = nums.length;
            int[] leftmin = new int[n];
            for (int i = 1, min = nums[0]; i < n; i++) {
                leftmin[i] = min;
                min = Math.min(min, nums[i]);
            }
            Stack<Pair> stack = new Stack<>();
            for (int i = 1; i < n; i++) {
                if (nums[i] <= leftmin[i]) {
                    continue;
                }
                Pair pair = new Pair(leftmin[i], nums[i]);
                while (!stack.isEmpty()) {
                    Pair peek = stack.peek();
                    if (nums[i] < peek.right && nums[i] > peek.left) {
                        return true;
                    }
                    if (nums[i] <= peek.left) {
                        break;
                    }
                    stack.pop();
                }
                stack.push(pair);
            }
            return false;
        }
        
        class Pair {
            int left;
            int right;
            Pair(int left, int right) {
                this.left = left;
                this.right = right;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.