LeetCode *456. 132模式（单调栈）

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int min_1 = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            for (int j = nums.size() - 1; j > i; j--) {
                if (min_1 < nums[j] && nums[j] < nums[i]) return true;
            }
            min_1 = min(min_1, nums[i]);
        }
        return false;
    }
};

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        vector<int> leftmin = vector<int>(nums.size());
        vector<int> st;
        int min_1;
        leftmin[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            leftmin[i] = min(leftmin[i - 1], nums[i]);
        }
        for (int i = nums.size() - 1; i >= 0; i--) {
            min_1 = INT_MIN;
            while (!st.empty() && nums[i] > st.back()) {
                min_1 = st.back();
                st.pop_back();
            }
            if (leftmin[i] < min_1) return true;
            st.push_back(nums[i]);
        }
        return false;
    }
};