Container With Most Water

Given $n$ non-negative integers $a_1, a_2, …, a_n$, where each represents a point at coordinate $(i, a_i)$. $n$ vertical lines are drawn such that the two endpoints of line $i$ is at $(i, a_i)$ and $(i, 0)$. Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and $n$ is at least 2.

O(nlogn) Version

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  return Math.max(fn(height), fn(height.concat().reverse()));
};

function fn(height) {
  var len = height.length;
  var ans = [];
  var index = [];
  var maxn = 0;

  for (var i = 0; i < len; i++) {
    if (!i) {
      ans.push(height[i]);
      index.push(i);
    } else {
      // 找到 ans 数组中刚好 >= height[i] 的元素位置
      // 返回其下标
      var pos = binarySearch(ans, height[i]);

      if (pos !== ans.length)
        maxn = Math.max(maxn, height[i] * (i - index[pos]));

      if (height[i] > ans[ans.length - 1]) {
        ans.push(height[i]);
        index.push(i);
      }
    }
  }

  return maxn;
}

function binarySearch(a, target) {
  target += 1;
  var start = 0
    , end = a.length - 1;

  while(start <= end) {
    var mid = ~~((start + end) >> 1);
    if (a[mid] >= target)
      end = mid - 1;
    else
      start = mid + 1;
  }

  if (a[start - 1] === target - 1)
    start -= 1;
  return start;
}

O(n) Version

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  var start = 0
    , end = height.length - 1
    , maxn = 0;

  while (start <= end) {
    maxn = Math.max(maxn, Math.min(height[end], height[start]) * (end - start));

    if (height[end] < height[start])
      end --;
    else
      start ++;
  }

  return maxn;
};

Contains Duplicates

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

/**
 * @param {number[]} nums
 * @return {boolean}
 */

var containsDuplicate = function(nums) {
  var hash = {};
  for(var i = 0, len = nums.length; i < len; i++) {
    if (hash[nums[i]]) return true;
    hash[nums[i]] = true;
  }
  return false;
};

Contains Duplicate II

Given an array of integers and an integer $k$, find out whether there are two distinct indices $i$ and $j$ in the array such that $nums[i] = nums[j]$ and the absolute difference between $i$ and $j$ is at most $k$.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */

var containsNearbyDuplicate = function(nums, k) {
  var pos = [];
  for(var i = 0, len = nums.length; i < len; i++) {
    if (pos[nums[i]] === undefined) 
      pos[nums[i]] = i;
    else {
      if (i - pos[nums[i]] <= k) 
        return true;
      pos[nums[i]] = i;
    }
  }

  return false;
};

Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices $i$ and $j$ in the array such that the absolute difference between $nums[i]$ and $nums[j]$ is at most t and the absolute difference between $i$ and $j$ is at most $k$.

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} t
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, k, t) {
  var len = nums.length;
  for (var i = 0; i < len; i++)
    for (var j = i + 1; j <= Math.min(i + k, len - 1); j++)
      if (Math.abs(nums[i] - nums[j]) <= t) return true;
  return false;
};