LeetCode第744题：寻找比目标字母最小的字母

题干

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

• 如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’

示例：

输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"
复制代码

解法1：指针

代码实现：

循环一次，记录目标值与数组中的大小情况，最后根据指针的值处理返回的值：

执行用时：84 ms, 在所有 JavaScript 提交中击败了87.12%的用户

内存消耗：40 MB, 在所有 JavaScript 提交中击败了13.63%的用户

  var nextGreatestLetter = function (letters, target) {
    let length = letters.length;
    let index = 0;
    for (let i = 0; i < length; i++) {
      if (letters[i].charCodeAt() > target.charCodeAt()) {
        index++
      }
    }
    return index==length||index==0?letters[0]:letters[length-index]
  };
复制代码

解法2：二分

使用二分查找的方式寻找目标值，最后看low指针的状态，如果low指针状态正常（小于数组长度），返回low指针位置元素（因为low自总是大于middle值），如果不正常返回数组第一个元素

代码实现：

执行用时：80 ms, 在所有 JavaScript 提交中击败了96.21%的用户

内存消耗：39.9 MB, 在所有 JavaScript 提交中击败了26.89%的用户

var nextGreatestLetter2 = function (letters, target) {
    let low = 0;
    let length = letters.length
    let high = letters.length - 1
    let middle = 0;
    while (low <= high) {
      middle = Math.floor((low + high) / 2);
      if (letters[middle].charCodeAt() > target.charCodeAt()) {
        high = middle - 1
      } else {
        low = middle + 1
      }
    }
    return low < length ? letters[low] : letters[0]
  };
复制代码