456. 132 Pattern - Medium

前往題目

想法

• stack

思路

挺難理解的一題，巧妙的運用monotonic stack

大致上是：利用monotonic stack，使推進去的數字遞減，只要當前數字比stack的頂端小，就pop，先當作132的2，因為3是當前數字，而下一個循環一開始就看當前是否比2還要小，如果是，就找到了

Code

✅ 99.35% Stack & Left Approach & Binary Search

class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack();
        int third = Integer.MIN_VALUE; // the second largest

        for (int i = nums.length - 1; i >= 0; --i) {
            // Found a pattern
            if (third > nums[i]) return true;
            // Maintain second largest number base on the current number
            // Which means take the current number as the largest number
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                third = stack.pop();
            }
            // Push current number
            stack.push(nums[i]);
        }
        return false;
    }
}