leetCode/162.寻找峰值.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>162. 寻找峰值</title>
  </head>
  <body>
    <script>
      // https://leetcode-cn.com/problems/find-peak-element/

      // 峰值元素是指其值严格大于左右相邻值的元素。
      // 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
      // 你可以假设 nums[-1] = nums[n] = -∞ 。
      // 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
      // 提示：
      // 1 <= nums.length <= 1000
      // -231 <= nums[i] <= 231 - 1
      // 对于所有有效的 i 都有 nums[i] != nums[i + 1]

      /**
       * @param {number[]} nums
       * @return {number}
       */
      var findPeakElement = function (nums) {};

      // --- answer-1 ---

      // 最大值一定是峰值 遍历
      var findPeakElement = function (nums = []) {
        let idx = 0;
        let length = nums.length;
        nums[length] = Number.NEGATIVE_INFINITY;
        for (let i = 1; i < length; i++) {
          if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            idx = i;
            break;
          }
        }
        return idx;
      };

      // --- answer-1 ---

      // --- answer-2 ---

      // 要求时间复杂度为 O(log n)

      var findPeakElement = function (nums = []) {
        if (nums.length === 1) return 0;
        if (nums.length === 2) {
          return nums[0] > nums[1] ? 0 : 1;
        }

        const min = Number.NEGATIVE_INFINITY;
        function find(nums, start, end) {
          if (start > end) return;
          let mid = (start + end) >> 1;
          let left = mid < 1 ? min : nums[mid - 1];
          let right = mid > nums.length - 2 ? min : nums[mid + 1];
          if (nums[mid] > left && nums[mid] > right) {
            return mid;
          }
          let f1 = find(nums, start, mid - 1);
          if (f1 != null) return f1;

          let f2 = find(nums, mid + 1, end);
          if (f2 != null) return f2;
          return;
        }

        return find(nums, 0, nums.length - 1);
      };

      // --- answer-2 ---

      var findPeakElement = function (nums) {
        const n = nums.length;
        let left = 0,
          right = n - 1,
          ans = -1;
        while (left <= right) {
          const mid = Math.floor((left + right) / 2);
          if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
            ans = mid;
            break;
          }
          if (compare(nums, mid, mid + 1) < 0) {
            left = mid + 1;
          } else {
            right = mid - 1;
          }
        }
        return ans;
      };

      // --- answer-3 ---

      // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
      // 方便处理 nums[-1] 以及 nums[n] 的边界情况
      const get = (nums, idx) => {
        if (idx === -1 || idx === nums.length) {
          return [0, 0];
        }
        return [1, nums[idx]];
      };

      const compare = (nums, idx1, idx2) => {
        const num1 = get(nums, idx1);
        const num2 = get(nums, idx2);
        if (num1[0] !== num2[0]) {
          return num1[0] > num2[0] ? 1 : -1;
        }
        if (num1[1] === num2[1]) {
          return 0;
        }
        return num1[1] > num2[1] ? 1 : -1;
      };

      // --- answer-3 ---

      var nums = [1, 2, 3, 1];
      var result = 2;
      // 解释：3 是峰值元素，你的函数应该返回其索引 2。

      var nums = [1, 2, 1, 3, 5, 6, 4];
      var result = 1; // 或 5 ;
      // 解释：你的函数可以返回索引 1，其峰值元素为 2；

      var nums = [1];
      var result = 0;

      var nums = [1, 2];
      var result = 1;

      var nums = [1, 4, 5, 6, 4];
      var result = 3;

      // var nums = [3, 2, 1];
      // var result = 0;

      // var nums = [1, 2, 3];
      // var result = 2;

      console.log('nums = ', nums);
      console.log('result = ', result);
      console.log('findPeakElement = ', findPeakElement(nums));
    </script>
  </body>
</html>