456.132-pattern.cpp

/*
 * @lc app=leetcode id=456 lang=cpp
 *
 * [456] 132 Pattern
 *
 * https://leetcode-cn.com/problems/132-pattern/description/
 *
 * algorithms
 * Medium (28.45%)
 * Total Accepted:    12.9K
 * Total Submissions: 45.1K
 * Testcase Example:  '[1,2,3,4]'
 *
 * 给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak <
 * aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
 * 
 * 注意：n 的值小于15000。
 * 
 * 示例1:
 * 
 * 
 * 输入: [1, 2, 3, 4]
 * 
 * 输出: False
 * 
 * 解释: 序列中不存在132模式的子序列。
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: [3, 1, 4, 2]
 * 
 * 输出: True
 * 
 * 解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
 * 
 * 
 * 示例 3:
 * 
 * 
 * 输入: [-1, 3, 2, 0]
 * 
 * 输出: True
 * 
 * 解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
 * 
 * 
 */
class Solution {
public:
    bool find132pattern(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 3)
            return false;

        vector<int> minstack(n, nums[0]);
        for (int i = 1; i < n; i++) {
            minstack[i] = min(minstack[i - 1], nums[i]);
        }
        // find i, j, j satisfy nums[i] < nums[k] < nums[j]
        stack<int> st;
        for (int j = n - 1; j >= 1; j--) {
            if (nums[j] > minstack[j]) {
                // satisfy nums[i] < nums[j]
                while(!st.empty() && st.top() <= minstack[j] ){
                    // to satisfy nums[k] > nums[i]
                    st.pop();
                }
                if (!st.empty() && st.top() < nums[j]) {
                    // satisfy nums[k] < nums[j]
                    return true;
                }
                st.push(nums[j]);
            }
        }
        return false;
    }
};