首页 🍒LeetCode,🐶算法

题目

FKqg2PbNE6.png

思路一:暴力法

遍历所有的“3”然后在“3”的右边遍历寻找“2”,找到返回true。也能过

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;
    }
};



文章评论