题目：
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况思路：基本思路，用一个栈保存数字，遇到数字推入栈，遇到字符，则取出栈顶的两个字符计算，并累加。用eval方便，不过内存消耗更大一点
时间复杂度：O(n)，空间复杂度(n)
/** * @param {string[]} tokens * @return {number} */ var evalRPN = function(tokens) { const pression = ["+", "-", "*", "/"]; const stack = []; for (const s of tokens) { if (pression.includes(s)) { const v2 = stack.pop(); const v1 = stack.pop(); switch (s) { case "+": stack.push(+v1 + +v2); break; case "-": stack.push(v1 - v2); break; case "*": stack.push(v1 * v2); break; case "/": stack.push(~~(v1 / v2)); break; } } else { stack.push(s); } } return stack[0]; };优化：可以从后往前递归处理。从后往前，遇到字符，说明前面要对两个数字的值进行操作，遇到数字则转为数字返回，减法和除法注意顺序问题
时间复杂度:O(n)，空间复杂度O(1)
/** * @param {string[]} tokens * @return {number} */ var evalRPN = function(tokens) { let fun = () => { let char = tokens.pop(); let num; switch (char) { case "+": return fun() + fun(); case "-": num = fun(); return fun() - num; case "*": return fun() * fun(); case "/": num = fun(); return ~~(fun() / num); default: return +char; } } return fun(); };题目：给定一个字符串，逐个翻转字符串中的每个单词。
思路：先用自带的方法，split分割然后反转
时间复杂度:O(n)，空间复杂度O(n)
/** * @param {string} s * @return {string} */ var reverseWords = function(s) { return s .trim() .split(" ") .filter((i) => i).reverse().join(" "); };也可以自己反转，就是把字符串推入一个数组，新成员放在开头
时间复杂度:O(n)，空间复杂度O(n)
/** * @param {string} s * @return {string} */ var reverseWords = function(s) { let left = 0; let right = s.length - 1; while (s[left] === " ") left++; while (s[right] === " ") right--; const res = []; let word = ""; while (left <= right) { if (s[left] === " " && word) { res.unshift(word); word = ""; } else if (s[left] !== " ") { word += s[left]; } left++; } res.unshift(word) return res.join(" "); };题目：给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
思路：乘积最大，因为0的特殊性，用0将数组分割成一个个小数组，对每一个小数组进行处理。如果数组的累积大于0，那么这个数就是最大乘积，如果小于0，从两边开始计算遇到第一个负数的乘积，左侧值更大，则除以左侧的乘积，反之右侧（负数越大，绝对值越小），最终对所有的子数组求最大值即可
时间复杂度:O(n)，空间复杂度O(n)
/** * @param {number[]} nums * @return {number} */ const maxP = (nums) => { if (nums.length < 2) return nums[0]; let max = nums.reduce((a, b) => a * b); if (max > 0) return max; let index = 0; let sumleft = 1; let sumRight = 1; while (sumleft > 0) { sumleft *= nums[index]; index++; } index = nums.length - 1; while (sumRight > 0) { sumRight *= nums[index]; index--; } if (sumleft > sumRight) return max / sumleft; return max / sumRight; }; var maxProduct = function (nums) { if (nums.length < 2) return nums[0]; const res = []; let temp = []; for (const n of nums) { if (n === 0 && temp.length) { res.push(temp); temp = []; } else if (n !== 0) { temp.push(n); } } if (temp.length) res.push(temp); return Math.max(...res.map((item) => maxP(item)), 0); };优化：转换思路，动态规划。乘积最大有两种情况，要么自身是正数，乘积就是前面数的最大乘积乘以自己。要么自身的负数，乘积就是前面数的最小值乘以自己，所以要保存最大的正数和最小的负数。当然为了区分0的情况，我们可以再将当前的积和自身比较，最终最后的结果就是最大值
时间复杂度:O(n)，空间复杂度O(1)
/** * @param {number[]} nums * @return {number} */ var maxProduct = function (nums) { let res = nums[0] let prevMin = nums[0] let prevMax = nums[0] let temp1 = 0, temp2 = 0 for (let i = 1; i < nums.length; i++) { temp1 = prevMin * nums[i] temp2 = prevMax * nums[i] prevMin = Math.min(temp1, temp2, nums[i]) prevMax = Math.max(temp1, temp2, nums[i]) res = Math.max(prevMax, res) } return res };题目：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
思路：先用自带的方法：
时间复杂度:O(n)，空间复杂度O(1)
/** * @param {number[]} nums * @return {number} */ var findMin = function(nums) { return Math.min(...nums) };然后可以用二分法。先比较开头和末尾的值的关系。如果开头的值小于末尾的值，相当于没有旋转，最小值就是开头的数。
取中点，比较中点和开头的值的关系。如果left的值小于middle的值，那么最小值在右半段（这说明left到middle一直是升序），反之在左半段
时间复杂度:O(logn)，空间复杂度O(1)
/** * @param {number[]} nums * @return {number} */ var findMin = function(nums) { let left = 0, right = nums.length - 1; if (nums[left] < nums[right]) return nums[0]; while (left !== right) { let middle = ~~((left + right) / 2); if (middle === left) { if (nums[left] > nums[right]) { left = right; } else { right = left; } } else if (nums[middle] > nums[left]) { left = middle; } else { right = middle; } } return nums[left]; };题目：
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
思路：先用迭代的方式，因为开头和末尾可视为负无穷，那么第一个比后面的数大的数就是峰值
时间复杂度:O(n)，空间复杂度O(1)
/** * @param {number[]} nums * @return {number} */ var findPeakElement = function(nums) { for (let i = 0; i < nums.length - 1; i++) { if (nums[i] > nums[i + 1]) { return i; } } return nums.length - 1; };也可以用二分法。如果middle的值比下一个值更大，那么肯定有个峰值在左侧，反之肯定有个峰值在右侧
时间复杂度:O(logn)，空间复杂度O(1)
/** * @param {number[]} nums * @return {number} */ var findPeakElement = function(nums) { let left = 0; let right = nums.length - 1; while (left < right) { let mid = ~~((left + right) / 2); if (nums[mid] > nums[mid + 1]) { right = mid; } else { left = mid + 1; } } return left; };
