快慢指针

环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
  if (head === null) return false;
  let fast = head, slow = head;
  while (fast) {
    fast = fast.next?.next;
    slow = slow.next;
    if (fast === slow) {
      break;
    }
  }
  return fast ? true: false;
};

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  let fast = head, slow = undefined, k = 1;
  while (k <= n) {
    fast = fast.next;
    k++;
  }
  while (fast) {
    slow = (!slow) ? head: slow.next;
    fast = fast.next;
  }
  if (slow) {
    slow.next = slow.next?.next;
  } else {
    head = head.next;
  }
  return head;
};

链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
  let fast = head, slow = undefined;
  while (fast?.next) {
    slow = (!slow) ? head : slow.next;
    fast = fast.next?.next;
  }
  return slow ? slow.next: head;
};

环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  if (head === null) return null;
  let fast = head, slow = head;
  while (fast) {
    fast = fast.next?.next;
    slow = slow.next;
    if (fast === slow) {
      break;
    }
  }
  if (fast) {
    let third = head;
    while (third !== slow) {
      third = third.next;
      slow = slow.next;
    }
    return third;
  }
  return null;
};

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
  let pA = headA, pB = headB;
  while (pA != pB) {
    pA = pA ? pA.next: headB;
    pB = pB ? pB.next: headA;
  }
  return pA;
};

相向指针

盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1
示例 3：

输入：height = [4,3,2,1,4]
输出：16
示例 4：

输入：height = [1,2,1]
输出：2

提示：

n = height.length
2 <= n <= 3 104
0 <= height[i] <= 3 104

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

两数之和 II - 输入有序数组

给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按递增顺序排列
-1000 <= target <= 1000
仅存在一个有效答案

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
  let l = 0, r = numbers.length - 1;
  while (l < r) {
    let sum = numbers[l] + numbers[r];
    if (sum === target) {
      return [l + 1, r + 1];
    } else if (sum > target) {
      r--;
    } else if (sum < target) {
      l++;
    }
  }
};

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  nums.sort((a, b) => a - b);
  let ans = [];
  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i-1]) {
      continue;
    }
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      let s = nums[i] + nums[l] + nums[r];
      if (s === 0) {
        ans.push([nums[i], nums[l], nums[r]]);
        l++;
        r--;
        while (l < r && nums[l-1] === nums[l]) {
          l++;
        }
        while (l < r && nums[r] === nums[r + 1]) {
          r--;
        }
      } else if (s > 0) {
        r--;
      } else if (s < 0) {
        l++;
      }
    }
  }
  return ans;
};

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
  nums.sort((a, b) => a - b);
  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i-1]) {
      continue;
    }
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      let s = nums[i] + nums[l] + nums[r];
      if (Math.abs(s - target) < Math.abs(ans - target)) {
        ans = s;
      }
      if (s === target) {
        return s;
      } else if (s > target) {
        r--;
      } else {
        l++;
      }
    }
  }
  return ans;
};

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109

-109 <= target <= 109

/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
nums.sort((a, b) => a - b);
let ans = [];
const dfs = (start, t, p) => {
  if (p.length === 4 && t === target) {
    ans.push([...p]);
    return;
  }

  for (let i = start; i < nums.length; i++) {
    if (nums.length - i < 4 - p.length) {
      return;
    }
    if (i > start && nums[i] === nums[i-1]) {
      continue;
    }
    if (t + nums[i] + (3 - p.length) * nums[i] > target) {
      return;
    }
    if (t + nums[i] + (3 - p.length) * nums[nums.length - 1] < target) {
      continue;
    }
    p.push(nums[i]);
    dfs(i + 1, t + nums[i], p);
    p.pop();
  }
};
dfs(0, 0, []);
return ans;
};

验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
解释：”amanaplanacanalpanama” 是回文串
示例 2:

输入: “race a car”
输出: false
解释：”raceacar” 不是回文串

提示：

1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  const t = s.toLowerCase();
  const st = new Set('abcdefghijklmnopqrstuvwxyz0123456789'.split(''));
  let l = 0; r = t.length-1;
  while (l <= r) {
    if (!st.has(t.charAt(l))) { l++; continue;}
    if (!st.has(t.charAt(r))) { r--; continue;}
    if (t.charAt(l) !== t.charAt(r)) return false;
    l++;
    r--;
  }
  return true;
};

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：

输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
  let l = 0, r = s.length - 1;
  while (l <= r) {
    [s[l], s[r]] = [s[r], s[l]];
    l++;
    r--;
  }
};

反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 ‘a’、’e’、’i’、’o’、’u’，且可能以大小写两种形式出现。

示例 1：

输入：s = “hello”
输出：”holle”
示例 2：

输入：s = “leetcode”
输出：”leotcede”

提示：

1 <= s.length <= 3 * 105
s 由可打印的 ASCII 字符组成

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function(s) {
  const ans = s.split('');
  const st = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
  let l = 0, r = ans.length - 1;
  while (l <= r) {
    if (!st.has(ans[l])) {l++; continue;}
    if (!st.has(ans[r])) {r--; continue;}
    [ans[l], ans[r]] = [ans[r], ans[l]];
    l++;
    r--;
  }
  return ans.join('');
};

658. 找到 K 个最接近的元素

给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3 输出：[1,2,3,4]
示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1 输出：[1,2,3,4]

提示：

1 <= k <= arr.length
1 <= arr.length <= 104

数组里的每个元素与 x 的绝对值不超过 104

解法一：// 二分 + 滑动窗口
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function(arr, k, x) {
let left = 0, right = arr.length - 1;
while (left + 1 < right) {
  let mid = left + ((right - left) >>> 1);
  if (arr[mid] >= x) {
    right = mid;
  } else {
    left = mid + 1;
  }
}
let p;
if (arr[right] === x) {
  p = right;
}
if (arr[left] === x) {
  p = left;
}
left = p >= k ? (p-k): 0;
right = (p + k) < arr.length ? (p + k ) : arr.length-1;
let sum = 0, min = Number.MAX_SAFE_INTEGER;
for (let i = left; i < left + k; i++) {
  sum += Math.abs(arr[i] - x);
}
min = sum;
let start = left;
for (let i = left + 1; i <= right; i++) {
  sum += Math.abs(arr[i + k - 1] - x) - Math.abs(arr[i - 1] - x);
  if (min > sum) {
    min = sum;
    start=i;
  }
}
return arr.slice(start, start + k);
};

解法二：// 左右指针
vector<int> findClosestElements(vector<int> nums, int k, int target) {
  int n = nums.size();
  // 「循环不变量」区间[left,right]上包含最优区间
  int left = 0, right = n - 1;
  for (int i = n - k; i > 0; --i) { // 采用「双指针对撞」
      if (target - nums[left] <= nums[right] - target)
          right--; // 去掉右边界
      else
          left++; // 去掉左边界
  }

  return vector<int>(nums.begin() + left, nums.begin() + left + k);
}

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。
示例：
输入: nums = [-2,0,1,3], target = 2 输出: 2 解释: 因为一共有两个三元组满足累加和小于 2: [-2,0,1] [-2,0,3]
进阶：是否能在 O(_n_2) 的时间复杂度内解决？

暴力 + 剪枝

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumSmaller = function(nums, target) {
  let ans = 0;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j+1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] < target) {
          ans++;
        }
      }
    }
  }
  return ans;
};

暴力 + 剪枝

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumSmaller = function(nums, target) {
  let ans = 0;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] * 3 >= target) {
      break;
    }
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] * 2 >= target) {
        break;
      }
      for (let k = j+1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] < target) {
          ans++;
        } else {
          break;
        }
      }
    }
  }
  return ans;
};

双指针：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumSmaller = function(nums, target) {
  let ans = 0;
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] * 3 >= target) {
      break;
    }
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      if (nums[l] + nums[r] + nums[i] < target) {
        ans += r - l;
        l++;
      } else {
        r--;
      }
    }
  }
  return ans;
};

有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按非递减顺序排序

进阶：请你设计时间复杂度为 O(n) 的算法解决本问题

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
  let l = 0, r = nums.length - 1, ans = [];
  while (l <= r) {
    let left = nums[l]*nums[l];
    let right = nums[r]*nums[r];
    if (left <= right) {
      ans.push(right);
      r--;
    } else {
      ans.push(left);
      l++;
    }
  }
  return ans.reverse();
};

有序转化数组

给你一个已经排好序的整数数组 nums 和整数 a、b、c。对于数组中的每一个数 x，计算函数值 f(x) = ax2 + bx + c，请将函数值产生的数组返回。

要注意，返回的这个数组必须按照升序排列，并且我们所期望的解法时间复杂度为 O(n)。

示例 1：

输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
输出: [3,9,15,33]
示例 2：

输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
输出: [-23,-5,1,7]

/**
 * @param {number[]} nums
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number[]}
 */
var sortTransformedArray = function(nums, a, b, c) {
  let ans = [];
  const compute = (i) => {
    return a*nums[i]*nums[i] + b*nums[i] + c;
  };

  if (a > 0) {
    let l = 0, r = nums.length - 1;
    while (l <= r) {
      let lm = compute(l);
      let rm = compute(r);
      if (lm <= rm) {
        ans.unshift(rm);
        r--;
      } else {
        ans.unshift(lm);
        l++;
      }
    }
  } else if (a < 0) {
    let l = 0, r = nums.length - 1;
    while (l <= r) {
      let lm = compute(l);
      let rm = compute(r);
      if (lm <= rm) {
        ans.push(lm);
        l++;
      } else {
        ans.push(rm);
        r--;
      }
    }
  } else if (a === 0) {
    if (b > 0) {
      for (let i = 0; i < nums.length; i++) {
        ans.push(compute(i));
      }
    } else if (b < 0) {
      for (let i = nums.length - 1; i >= 0; i--) {
        ans.push(compute(i));
      }
    } else {
       ans = new Array(nums.length).fill(c);
    }
  }
  return ans;
};

比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：

输入：S = “ab##”, T = “c#d#”
输出：true
解释：S 和 T 都会变成 “”。
示例 3：

输入：S = “a##c”, T = “#a#c”
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：

输入：S = “a#c”, T = “b”
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 ‘#’。

进阶：

你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解法一：先收缩字符串

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
  const shrink = (str) => {
    let ans = '', lc = 0;
    let l = str.length - 1;
    while (l >= 0) {
      let ch = str.charAt(l--);
      if (ch === '#') {
        lc++;
        continue;
      }
      if (lc > 0) {
        lc--;
        continue;
      }
      ans = ch + ans;
    }
    return ans;
  }
  return shrink(s) === shrink(t);
};

解法二：双指针：

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
  let l = s.length - 1, r = t.length - 1, lc = 0, rc = 0;
  while (l >= 0 || r >= 0) {
    while (l >= 0 && (lc > 0 || s.charAt(l) === '#')) {
      if (s.charAt(l) === '#') { lc++; l--; continue;}
      if (lc > 0) { lc--; l--; continue;}
      break;
    }
    while (r >= 0 && (rc > 0 || t.charAt(r) === '#')) {
      if (t.charAt(r) === '#') { rc++; r--; continue;}
      if (rc > 0) { rc--; r--; continue;}
      break;
    }
    if (l === -1 && r === -1) {
      return true;
    }
    if (l === -1 || r === -1) {
      return false;
    }
    if (s.charAt(l) !== t.charAt(r)) {
      return false;
    }
    l--;
    r--;
  }
  return true;
};

数组中的最长山脉

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < … B[i-1] < B[i] > B[i+1] > … > B[B.length - 1]
（注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
示例 2：

输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

0 <= A.length <= 10000
0 <= A[i] <= 10000

解法一：单调栈

/**
 * @param {number[]} arr
 * @return {number}
 */
var longestMountain = function(arr) {
  let st = [], r = 0, ans = 0;
  while (r < arr.length) {
    if (st.length && arr[st[st.length - 1]] > arr[r]) {
      let left = st.length;
      // 向后寻找单调递减栈的边界。
      while (r < arr.length && arr[st[st.length - 1]] > arr[r]) {
        st.push(r++);
      }
      // 计算栈中的元素的个数，注意，如果原来栈中只有一个元素，则说明没有左侧的单调上升序列。不符合山峰的定义，要过滤掉。
      ans = Math.max(ans, left > 1 ? st.length : 0);
      r--;
      st.length = 0;
    } else if (st.length && arr[st[st.length - 1]] === arr[r]) {
      st.length = 0;
    }
    st.push(r++);
  }
  return ans;
};

解法二：单调栈的空间优化版本，由于只需要栈顶的最大值，所以保留一个栈顶的元素下标，和栈的起始下标即可。

/**
 * @param {number[]} arr
 * @return {number}
 */
var longestMountain = function(arr) {
  let st = 0, lc = 0, r = 0, ans = 0;
  while (r < arr.length) {
    if (arr[st] > arr[r]) {
      let top = st;
      while (r < arr.length && arr[top] > arr[r]) {
        top = r++;
      }
      ans = Math.max(ans, (st > lc) ? (r - lc) : 0);
      r--;
      lc = r;
    } else if (arr[st] === arr[r]) {
      lc = r;
    }
    st = r++;
  }
  return ans;
};

881. 救生艇

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1：
输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2)
示例 2：
输入：people = [3,2,2,1], limit = 3 输出：3 解释：3 艘船分别载 (1, 2), (2) 和 (3)
示例 3：
输入：people = [3,5,3,4], limit = 5 输出：4 解释：4 艘船分别载 (3), (3), (4), (5)
提示：

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
```
/**
* @param {number[]} people
* @param {number} limit
* @return {number}
*/
var numRescueBoats = function(people, limit) {
people.sort((a, b) => a - b);
let l = 0, r = people.length - 1, ans = 0;
while (l <= r) {
  // 左右搭配，尝试最佳组合
  if (people[l] + people[r] <= limit) {
    l++;
  }
  ans ++;
  r--;
}
return ans;
};
```
516. 最长回文子序列
难度中等611收藏分享切换为英文接收动态反馈
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = “bbbab” 输出：4 解释：一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入：s = “cbbd” 输出：2 解释：一个可能的最长回文子序列为 “bb” 。

提示：

1 <= s.length <= 1000

s 仅由小写英文字母组成 ```javascript class Solution { int[][] mem; public int longestPalindromeSubseq(String s) {

  // 双指针
  int n = s.length();
  mem = new int[n][n];
  for (int i = 0; i < n; i ++)
      Arrays.fill(mem[i], -1);
  int l = 0, r = n - 1;
  return dfs(s, l, r);

} private int dfs(String s, int l, int r) {

  if (mem[l][r] != -1) return mem[l][r];
  int ans = 0;
  if (l == r) return 1;
  if (l > r) return 0;
  if (s.charAt(l) == s.charAt(r)) {
      ans = 2 + dfs(s, l+1, r-1);
  } else {
      ans = Math.max(dfs(s, l+1, r), dfs(s, l, r-1));
  }
  mem[l][r] = ans;
  return ans;

} }

作者：ydq-2 链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/shuang-zhi-zhen-ji-yi-hua-dfs-si-lu-jian-xypy/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

<a name="LZrlY"></a>
# 删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。



说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝<br />int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。<br />// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。<br />for (int i = 0; i < len; i++) {<br />    print(nums[i]);<br />}<br /> <br />示例 1：

输入：nums = [1,1,2]<br />输出：2, nums = [1,2]<br />解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。<br />示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]<br />输出：5, nums = [0,1,2,3,4]<br />解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。<br /> 

提示：

0 <= nums.length <= 3 * 104<br />-104 <= nums[i] <= 104<br />nums 已按升序排列<br /> 

作者：力扣 (LeetCode)<br />链接：[https://leetcode-cn.com/leetbook/read/sliding-window-and-two-pointers/owkrrm/](https://leetcode-cn.com/leetbook/read/sliding-window-and-two-pointers/owkrrm/)<br />来源：力扣（LeetCode）<br />著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  let len = nums.length;
  if (len < 2) return len;
  // 右指针，初始化为1，从第二个开始判断，由于是有序，所以第一个肯定不重复
  let right = 1; // [1, len-1]
  // 左指针，初始化为0，指向写入的位置。
  let left = 0; // [0, anslen)
  // 右指针前进循环
  while (right < len) {
    // 左右指针条件判断，决定是否移动左指针
    if (nums[right] !== nums[left]) {
      // 需要写入数据，所以要先++，给新数据新的位置写入
      left++;
       // 判断重复，只需要两个指针判断即可，若不重复，则复制元素向前移动。
      nums[left] = nums[right];
    }
    // 右指针移动，
    right++;
  }
  // j代表写入的最后一个位置，j+1即为去重后的字符串长度。
  return left+1;
};

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sliding-window-and-two-pointers/owzh97/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
  // left: [0, newlen]
  // right: [0, len)
  let left = 0, right = 0;
  while (right < nums.length) {
    // 左指针移动条件：当前值与目标值不等。
    if (nums[right] !== val) {
      // 移动到左指针指向的位置，只是删除数据，所以用带写入数据替换被删数据内容，再left++。
      nums[left] = nums[right];
      // 左指针移动，指向新的待写入数据的下标，若无数据写入，则left结果即为新数组长度
      left++;
    }

    // 右指针移动
    right++;
  }
  // 循环退出时：right：|nums|， left：|nums| 不含val
  return left;
};

例题：最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
提示：

0 \le nums.length \le 10^40≤nums.length≤10
4
-10^9 \le nums[i] \le 10^9−10
9
≤nums[i]≤10
9

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sliding-window-and-two-pointers/rlv8hj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
  // left: [0, maxLeStringLeft]
  // right: [1, len)， 第一个字符一定不重复
  // ans: 子串长度 = right - left
  let left = 0, right = 1, ans = right -left;
  while (right < nums.length) {
    if (nums[right-1] >= nums[right]) {
      // 不满足单调性，直接将左指针跳转到right位置。之前的数据全部忽略，相当单调栈中，清空栈空间。
      left = right;
    }
    // 开区间写法：先++，后计算区间长度
    right++;
    ans = Math.max(ans, right - left);

    // 闭区间写法：先计算长度，后++；
    // ans = Math.max(ans, right - left + 1);
    // right++;
  }
  return ans;
};

75. 颜色分类

难度中等975收藏分享切换为英文接收动态反馈
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：
输入：nums = [0]
输出：[0]

示例 4：
输入：nums = [1]
输出：[1]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：
你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
  // 循环不变量
  // [0, p1) = 0
  // [p1, p2) = 1
  // [p2, len-1] = 2
  let p1 = -1; // 左指针，指向 最后一个0的的位置下标
  let p2 = nums.length; // 右指针，指向 第一个2的的位置下标
  let i = 0; // 快指针，（主循环变量），
  const swap = (a, b) => [nums[a], nums[b]] = [nums[b], nums[a]];

  // 在识别出0，2，分别交换到对应区域，并更新指针。
  while ( i < p2) {
    if (nums[i] === 0) {
      ++p1;
      swap(i, p1);
      i++;
    } else if (nums[i] === 1) {
      i++;
    } else if (nums[i] === 2) {
      --p2;
      swap(i, p2);
    }
  }
};

215. 数组中的第K个最大元素

难度中等1232收藏分享切换为英文接收动态反馈
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  const swap = (l, r) => [nums[l], nums[r]] = [nums[r], nums[l]];

  const comparator = (a, b) => {
    return a > b;
  };

  // 标准快排的分区函数，以最后一个节点为分区点，
  const partition = (l, r, k) => {
    // [l, i) < x ， 保持数组前面为大于x的值
    // i = x         x的值所在位置
    // (i, r) > x    数组后半段为小于x的数值，这三个即为该分区函数的循环不变量。
    // i: 慢指针，指向所在位置，若发现某个j对应的值比x小，则向后移动x。
    // j: 快指针(主循环指针）,区间元素访问循环下标变量。
    // x: 临时变量保存分区点数值，分区结束后，再回写到i的位置。
    let x = nums[r-1], i = l, j = l;
    while (j < r-1) {
      if (comparator(nums[j], x)) {
        swap(i, j);
        i++;
      }
      j++;
    }
    // x的值回写。
    swap(i, r-1);
    // i即为分区点坐标。
    return i;
  };

  const getK = (left, right, k) => {
    while (true) {
      let nextLeft = partition(left, right, k);
      let len = nextLeft - left + 1;
      if (k === len) {
        return nums[nextLeft];
      } else if (k < len) {
        right = nextLeft;
      } else if (k > len) {
        left = nextLeft + 1;
        k -= len;
      }
    }
  }
  return getK(0, nums.length, k);
};