# LeetCode - 困难

/**
 * 使用栈解决
 * @param {string} s
 * @return {number}
 */
const longestValidParentheses = s => {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') stack.push(i);
    else {
      if (stack.length && s[stack[stack.length - 1]] === '(') stack.length--;
      else stack.push(i);
    }
  }

  if (!stack.length) return s.length;
  let longest = 0;
  let end = s.length;
  let start = 0;
  while (stack.length) {
    start = stack[stack.length - 1];
    stack.length--;
    longest = Math.max(longest, end - start - 1);
    end = start;
  }
  longest = Math.max(longest, end);
  return longest;
};

/**
 * 找至高点，从两侧向至高点靠拢
 * @param {number[]} height
 * @return {number}
 */
const trap = height => {
  if (!height) {
    return 0;
  }

  const len = height.length;
  let maxHeight = height[0];
  let maxIndex = 0;

  for (let i = 1; i < len; i++) {
    if (height[i] > maxHeight) {
      maxHeight = height[i];
      maxIndex = i;
    }
  }

  let area = 0;
  let lastWall = height[0];

  // 从左侧到至高
  for (let i = 1; i < maxIndex; i++) {
    if (height[i] < lastWall) {
      area += lastWall - height[i];
    } else {
      lastWall = height[i];
    }
  }

  lastWall = height[len - 1];
  // 从右侧到至高
  for (let j = len - 2; j > maxIndex; j--) {
    if (height[j] < lastWall) {
      area += lastWall - height[j];
    } else {
      lastWall = height[j];
    }
  }

  return area;
};

/** 有限状态机,游戏AI算法常用到
 * @param {string} s
 * @return {boolean}
 */
const isNumber = s => {
  if (!s) {
    return s;
  }

  // 定义枚举状态
  const INVALID = 0;
  const SPACE = 1;
  const SIGN = 2;
  const DIGIT = 3;
  const DOT = 4;
  const EXPONENT = 5;

  // 定义转换表,8个状态，6种输入类别分别可以进行转换
  const transitionTable = [
    [-1, 0, 3, 1, 2, -1], // 0
    [-1, 8, -1, 1, 4, 5], // 1
    [-1, -1, -1, 4, -1, -1], // 2
    [-1, -1, -1, 1, 2, -1], // 3
    [-1, 8, -1, 4, -1, 5], // 4
    [-1, -1, 6, 7, -1, -1], // 5
    [-1, -1, -1, 7, -1, -1], // 6
    [-1, 8, -1, 7, -1, -1], // 7
    [-1, 8, -1, -1, -1, -1] // 8
  ];

  const getInputType = ch => {
    if (ch === ' ') {
      return SPACE;
    } else if (ch === '+' || ch === '-') {
      return SIGN;
    } else if (ch >= '0' && ch <= '9') {
      return DIGIT;
    } else if (ch === '.') {
      return DOT;
    } else if (ch === 'e' || ch === 'E') {
      return EXPONENT;
    }

    return INVALID;
  };

  const len = s.length;
  let index = 0;
  let state = 0;

  while (index < len) {
    const ch = s.charAt(index);
    const inputType = getInputType(ch);

    state = transitionTable[state][inputType];

    if (state === -1) {
      return false;
    }

    index++;
  }

  return state === 1 || state === 4 || state === 7 || state === 8;
};