[leetcode] 456. 132 Pattern (Medium)

对一个三个元素以上的数组，如果存在1-3-2模式的组合，则返回true。

1-3-2模式就是值的排序是i<k<j但是下标排序是i<j<k。

解法一：

硬解，利用一个变量存储是否找到了较大值和较小值，因为是1-3-2，所以从后往前遍历才能找到较当前值更大和更小的值。

Runtime: 648 ms, faster than 12.76% of C++ online submissions for 132 Pattern.

class Solution

{

public:

  bool find132pattern(vector<int> &nums)

  {

    if (nums.size() < )

      return false;

    int a = ;

    int times = ;

    for (int i = nums.size()-; i > ; --i)

    {

      a = nums[i];

        times=;

      for (int j = i - ; j >=; --j)

      {

        if (nums[j] > a && times == )

          times++;

        if (nums[j] < a && times == )

          times++;

      }

      if(times==)

        return true;

    }

    return false;

  }

};

解法二：

利用栈，这里涉及到一个栈排序的知识，看一下有助于理解。

class Solution

{

public:

  bool find132pattern(vector<int> &nums)

  {

    stack<int> s;

    int prev = INT_MIN;

    for (int i = nums.size() - ; i >= ; i--)

    {

      while (!s.empty() && s.top() < nums[i])

      {

        if (prev > s.top())

          return true;

        prev = s.top();

        s.pop();

      }

      s.push(nums[i]);

    }

    return !s.empty() && prev > s.top();

  }

};

巴特西

[leetcode] 456. 132 Pattern (Medium)

最新文章

热门文章