Ограничения:

  • n == nums.length
  • 1 <= n <= 2 * 105
  • -10^9 <= nums[i] <= 10^9

Решение

Чтобы проверить шаблон 132 в массиве целых чисел, мы можем использовать стек для отслеживания потенциального второго целого числа и переменную для отслеживания потенциального третьего целого числа. Мы начинаем с перебора массива в обратном порядке и для каждого элемента проверяем, меньше ли он потенциального третьего целого числа. Если это так, мы возвращаем true, так как нашли шаблон 132. Если нет, мы проверяем, больше ли элемент потенциального второго целого числа. Если это так, мы обновляем потенциальное третье целое число для элемента. Наконец, мы помещаем элемент в стек, который служит нашим потенциальным вторым целым числом.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
//Metehan Homriş
var find132pattern = function find132pattern(nums) {
    let stack = [nums[nums.length - 1]]; // initialize stack with last element
    let third = Number.MIN_SAFE_INTEGER; // initialize third to smallest possible value
    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < third) { // check if current element is less than third
            return true; // found a 132 pattern
        }
        while (stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            third = stack.pop(); // update third to last element in stack
        }
        stack.push(nums[i]); // push current element to stack
    }
    return false; // no 132 pattern found
}

В этом коде мы начинаем с инициализации стека последним элементом массива и переменной «третий» с наименьшим возможным значением. Затем мы перебираем массив в обратном порядке, проверяя, меньше ли текущий элемент, чем «третья» переменная. Если это так, мы возвращаем true, так как нашли шаблон 132. Если нет, мы проверяем, больше ли текущий элемент, чем последний элемент в стеке. Если это так, мы обновляем «третью» переменную до последнего элемента в стеке и удаляем его из стека. Наконец, мы помещаем текущий элемент в стек, который служит нашим потенциальным вторым целым числом.

Мы повторяем этот процесс для каждого элемента в массиве, и если мы достигнем конца массива, не найдя шаблона 132, мы вернем false.

Автор Метехан Хомриш