有效括号问题（LeetCode 20）

题目描述：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。

示例：
输入: “()”，输出: true
输入: “()[]{}”，输出: true
输入: “(]”，输出: false
输入: “([)]”，输出: false
输入: “{[]}”，输出: true
思路分析：
题目中若涉及括号问题，则很有可能和栈相关，
遍历字符串，遇到”左括号”，就把匹配的”右括号”推入栈中，遍历到右括号时，右括号如果不等于栈顶元素，说明无效，若相等，则栈顶元素推出，重复上面操作，最后若所有括号都能配对，栈应该为空

  1. var isValid = function(s) {
  2.   const hash = {
  3.     '[': ']',
  4.     '{': '}',
  5.     '(': ')'
  6.   }
  7.   const stack = []
  8.   const len = s.length
  9.   const left = ['(', '[', '{']
  10.   for(let i=0; i<len; i++){
  11.     if(left.includes(s[i])){
  12.       stack.push(hash[s[i]])
  13.     }else{
  14.       if(stack.pop() !== s[i]){
  15.         return false
  16.       }
  17.     }
  18.   }
  19.   return !stack.length
  20. };

每日温度问题（LeetCode 739）

题目描述: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

示例：
给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
输出应该是[1, 1, 4, 2, 1, 1, 0, 0]
提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
思路分析：
遍历列表，如果元素递减，则维持一个递减栈，栈中储存递减元素的索引，直到遍历到打破递减的元素a，
此时栈顶元素是b，结果数组是 res ，则res[a] = b-a，且 b 要出栈

过程动图参考： 每日温度问题

var dailyTemperatures = function(temperatures) {
  const len = temperatures.length
  const res = new Array(len).fill(0)
  const stack = [] // 递减栈
  for(let i=0; i<len; i++){
    while(stack.length && temperatures[i] > temperatures[stack[stack.length -1]]){
      const top = stack.pop() 
      res[top] = i - top
    }
    stack.push(i)
  }
  return res
};

最小栈问题（LeetCode 155）

题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中 top() —— 获取栈顶元素 pop() —— 弹出栈顶元素 getMin() —— 检索栈中的最小元素

示例:

const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); //返回 -3.
minStack.pop();
minStack.top();// 返回 0.
minStack.getMin(); // 返回 -2.

思路分析：
要求常数时间内检索到最小元素——时间复杂度为O(1)，需要声明一个辅助栈 stack2，在元素入栈push的时候同时在stack2 维持一个递减栈，栈顶元素就是 minValue，不过需要注意pop()的时候，如果出栈的是minValue，stack2 的栈顶元素也要出栈

var MinStack = function() { 
  this.stack = []
  this.stack2 = [] // 辅助递减栈
};

MinStack.prototype.push = function(val) {
  this.stack.push(val)
  if(!this.stack2.length || val <= this.stack2[this.stack2.length - 1]){
    this.stack2.push(val)
  }
};

MinStack.prototype.pop = function() {
  if(this.stack.pop() === this.stack2[this.stack2.length -1]){
    this.stack2.pop()
  }
};

MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1]
};

MinStack.prototype.getMin = function() {
  return this.stack2[this.stack2.length -1]
};