【JavaScript】LeetCode：11-15

11 最长连续序列

• 数组排序、去重
• 遍历数组中的元素，当元素连续时，长度加1，当不连续时，长度设置为1。

/*** @param {number[]} nums* @return {number}*/
var longestConsecutive = function(nums) {if(nums.length == 0){return 0;}var num_new = Array.from(new Set(nums.sort((a, b) => a - b)));var target = 1;var temp = 1;for(var i = 0; i < nums.length; i++){if(num_new[i + 1] == num_new[i] + 1){temp += 1;target = Math.max(target, temp);}else{temp = 1;}}return target;
};

12 移动零

• 双指针
• 遍历数组，如果元素 i 不是0，就赋值给 j，并把 i 位置的元素设置为0（注意：当 j 和 i 不同时）。

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var moveZeroes = function(nums) {var j = 0;for(var i = 0; i < nums.length; i++){if(nums[i] != 0){nums[j] = nums[i];if(j != i){nums[i] = 0;}j++;}}
};

13 盛最多水的容器

• 双指针（难想）
• 面积 = 两块板的横坐标距离 * 短板长度。
• 总是移动指向短板的指针。
  若移动指向长板的指针：
  (1) 假设 i ，j - 1，j 三个板子分别为：3，…，5，8，移动前min(i，j) = i，移动后min(i，j - 1) = i。
  (2) 假设 i ，j - 1，j 三个板子分别为：3，…，9，8，移动前min(i，j) = i，移动后min(i，j - 1) = i。
  (3) 假设 i ，j - 1，j 三个板子分别为：3，…，2，8，移动前min(i，j) = i，移动后min(i，j - 1) = j - 1 < i。
  综上所述：若移动指向长板的指针，min(i，j - 1) ≤ min(i，j)，短板长度更小，使得面积更小，因此不可取。

/*** @param {number[]} height* @return {number}*/
var maxArea = function(height) {var n = height.length;var i = 0, j = n - 1;var res = 0;while(i < j){res = Math.max(res, Math.min(height[i], height[j]) * (j - i));if(height[i] < height[j]){i++;}else{j--;}}return res;
};

14 三数之和

• 双指针
• 按照升序排序，若排序后的第一个数 > 0，直接返回[ ]，因为无论如何也不可能存在3个数之和等于0的结果。
• k为当前位置，i = k + 1，j = nums.length - 1。
• 若nums[k] + nums[i] + nums[j] = 0，i 和 j 向内收缩（i++，j–），跳过相同的元素。
• 若nums[k] + nums[i] + nums[j] > 0，j–。
• 若nums[k] + nums[i] + nums[j] < 0，i++。

/*** @param {number[]} nums* @return {number[][]}*/
var threeSum = function(nums) {nums.sort((a, b) => a - b);var res = [];for(var k = 0; k < nums.length - 2; k++){if(nums[k] > 0) {  return res;  }if(k > 0 && nums[k] == nums[k - 1]){continue;}var i = k + 1; var j = nums.length - 1;while(i < j){var sum = nums[k] + nums[i] + nums[j];if(sum == 0){res.push([nums[k], nums[i], nums[j]]);while(i < j && nums[i] == nums[i + 1]){i++;}while(i < j && nums[j] == nums[j - 1]){j--;}i++;j--;}else if(sum > 0){j--;}else{i++;}}     }return res;
};

15 接雨水

• 单调栈
• 从栈头到栈尾，构造一个单调递增栈，这里栈中存放元素的索引值。
• 遍历数组，若当前元素 < 栈头元素，入栈。
• 若当前元素 > 栈头元素，说明此时构成了一个“凹槽”，将栈头元素弹出并保存(mid)，凹槽的右边界为当前元素，左边界为新栈头元素，此时就可以计算雨水的面积了。
• h = min(height[左边界]，height[右边界]) - height[mid]
  w = 右边界 - 左边界 - 1
  s = h * w

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {const stack = [];let res = 0;stack.push(0);for(let i = 1; i < height.length; i++){if(height[i] <= height[stack[stack.length - 1]]){stack.push(i);}else{while(stack.length > 0 && height[i] > height[stack[stack.length - 1]]){let mid = stack.pop();if(stack.length != 0){let right = height[i];let left = height[stack[stack.length - 1]];let h = Math.min(left, right) - height[mid];let w = i - stack[stack.length - 1] - 1;res += h * w;}}stack.push(i);}}return res;
};