485. 最大连续 1 的个数

思路

双指针遍历找到当前连续的长度，并保存最大值

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var findMaxConsecutiveOnes = function(nums) {
  6.   let l = 0, r = 0, ret = 0;
  7.   const len = nums.length
  8.   while(r < len) {
  9.     if (!nums[r]) {
  10.       l = r + 1;
  11.       r++;
  12.     } else {
  13.       r++;
  14.       ret = Math.max(ret, r - l)
  15.     }
  16.   }
  17.   return ret;
  18. };

复杂度分析

时间复杂度 数组的遍历 - 图1#card=math&code=O%28N%29)
空间复杂度 数组的遍历 - 图2#card=math&code=O%281%29)

495. 提莫攻击

思路

双指针，每次改变当前的持续时间范围，找到最新可持续时间

代码

  1. /**
  2.  * @param {number[]} timeSeries
  3.  * @param {number} duration
  4.  * @return {number}
  5.  */
  6. var findPoisonedDuration = function(timeSeries, duration) {
  7.     let start = 0, end = 0, count = 0;
  8.     for(let i = 0; i < timeSeries.length; i ++) {
  9.       let cur = timeSeries[i], curEnd = cur + duration;
  10.       if (cur > end) {
  11.         start = cur;
  12.         end = curEnd;
  13.         count += duration
  14.       } else {
  15.         start = end;
  16.         end = curEnd;
  17.         count += end - start;
  18.       }
  19.     }
  20.     return count;
  21. };

复杂度分析

时间复杂度 数组的遍历 - 图3#card=math&code=O%28N%29)
空间复杂度 数组的遍历 - 图4#card=math&code=O%281%29)

414. 第三大的数

思路

遍历比大小

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var thirdMax = function(nums) {
  6.   let min = Number.MIN_SAFE_INTEGER, mid = Number.MIN_SAFE_INTEGER, max = Number.MIN_SAFE_INTEGER, len = nums.length
  7.   for(let i = 0; i < len; i ++) {
  8.     let cur = nums[i];
  9.     if (cur < min) continue;
  10.     if (cur > max) {
  11.       min = mid;
  12.       mid = max;
  13.       max = cur;
  14.     } else if (cur > mid && cur < max) {
  15.       min = mid;
  16.       mid = cur;
  17.     } else if (cur > min && cur < mid) {
  18.       min = cur;
  19.     }
  20.   }
  21.   return (len >= 3 && min != Number.MIN_SAFE_INTEGER) ? min : max;
  22. };

复杂度分析

时间复杂度 数组的遍历 - 图5#card=math&code=O%28N%29)
空间复杂度 数组的遍历 - 图6#card=math&code=O%281%29)

628. 三个数的最大乘积

思路

先排序。然后考虑有负数和都为正的情况。

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var maximumProduct = function(nums) {
  6.   nums = nums.sort((a, b) => a - b)
  7.   let len = nums.length
  8.   return Math.max(nums[0] * nums[1] * nums[len-1], nums[len-3]*nums[len-2]*nums[len-1])
  9. };

复杂度分析

时间复杂度 数组的遍历 - 图7#card=math&code=O%28nlogN%29)
空间复杂度 数组的遍历 - 图8#card=math&code=O%281%29)