單調(diào)棧 03

LeetCode 456

https://leetcode-cn.com/problems/132-pattern/

單調(diào)棧

• 需要一個 preMin[n] 來記錄 0 ~ i 區(qū)間內(nèi)最小的數(shù)，即 132模式的 “1”
• 需要一個棧 stack 從后向前遍歷，去找 “3”
• 至于那個 “2” 就是在從后向前遍歷的過程中，num[i] 充當(dāng)?shù)慕巧?。找到直接返回?/li>

import java.util.*;

public class Solution {

    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        int[] preMin = new int[n];  // 0 ~ i the smallest num
        preMin[0] = nums[0];
        for (int i = 1; i < n; i++)
            preMin[i] = Math.min(preMin[i - 1], nums[i]);
        // the stack store num bigger than preMin[i] and smaller than num[i]
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = n - 1; i >= 0; i--) { // from tail to head traversal update stack
            if (nums[i] > preMin[i]) {
                // peek num smaller than all front of num is illicit
                while (!stack.isEmpty() && stack.peek() <= preMin[i])
                    stack.pop();
                // judge whether find 132 pattern
                if (!stack.isEmpty() && stack.peek() < nums[i]) // 3(peek) < 2(num[i])
                    return true;
                stack.push(nums[i]);    // not find, push the num that smaller than preMin[i] into stack
            }
        }
        return false;
    }

}