Java教程

LeetCode题解:456. 132 模式,n平方暴力,JavaScript,详细注释

本文主要是介绍LeetCode题解:456. 132 模式,n平方暴力,JavaScript,详细注释,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接:456. 132 模式

解题思路:

  1. 该题的条件是:i < j < knums[i] < nums[k] < nums[j]
  2. 可以理解为,在已知nums[i]nums[j]的情况下,查找是否存在nums[k],满足条件nums[i] < nums[k] < nums[j]
  3. nums[i]可以用变量numsi缓存,始终存储从nums[0]nums[j-1]之间的最小值。
  4. 因此只需要用第一层循环,不断查找nums[j],同时缓存numsi
  5. 用第二层循环,在j+1nums.length - 1的范围内查找是否有满足条件的nums[k]
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function (nums) {
  let numsi = nums[0]; // 存储题目中的nums[i],初始值是nums[0]

  // 不断查找nums[j],初始值是nums[1]
  for (let j = 1; j < nums.length; j++) {
    // 在已知nums[i]、nums[j]的基础上,查找是否存在满足条件的nums[k]
    // k的索引必然在j到nums.length-1之间
    for (let k = j + 1; k < nums.length; k++) {
      // 满足nums[i] < nums[k] < nums[j]条件,表示找到132模式子序列
      if (numsi < nums[k] && nums[k] < nums[j]) {
        return true;
      }
    }

    // nums[i]始终是nums[0]~nums[j-1]中的最小值
    numsi = Math.min(numsi, nums[j]);
  }

  // 退出循环,则表示没有找到132模式子序列
  return false;
};
这篇关于LeetCode题解:456. 132 模式,n平方暴力,JavaScript,详细注释的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!