有效的括号

原题链接点这去练手
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

思路

其实就是要左右配对并且中间没有别的“电灯泡”，那首先排除奇数长度的，然后遍历字符串，一个字符一判断，把左边的符号压入栈去，右边的符号和最近的压入栈的栈顶比较是不是一对，是就出栈，如此遍历完查看栈里还有没有剩余了，若没有就符合题意，反之就false；那可不可以右边的符号入栈，左边的去参与判断，不行，可以假设一下会试试嗷~~

AC代码（js）

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if(s.length%2!==0){//若字符串长度是奇数肯定不符合题意
    return false
  }
  let stack=[]
  for(let i=0;i<s.length;i++){
      if(s[i]==='('||s[i]==='{'||s[i]==='['){
          stack.push(s[i])//压入栈，成为新的栈顶元素
      }
      else if(s[i]===')'&& stack[stack.length-1]==='('){
        stack.pop()//匹配到就出栈
      }
      else if(s[i]==='}'&& stack[stack.length-1]==='{'){
        stack.pop()
      }
      else if(s[i]===']'&& stack[stack.length-1]==='['){
        stack.pop()
      }
      else{
          return false
      }
    }
    if(stack.length===0)return true
      else return false
};

验证栈序列

原题链接点这去练手
给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

思路：

说白了就像判断出入栈顺序是否合法，遵循先进后出，后进先出的原则。定义一个空栈，放pushed的元素，每次拿最后入空栈的元素和poped的第一个元素比较，直到相等就让空栈中这个元素出栈，poped的第一个元素删掉，其实就是pushed的尾和poped的头的比较，最后看空栈的全部出栈了没，全出了说明都按原则出栈，还剩元素则false
AC代码（js）

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
let stack=[]//空栈
for(let i of pushed){/chu/遍历pushed
stack.push(i)
while(popped[0]===stack[stack.length-1]&&stack.length){
stack.pop()
popped.shift()//把匹配完的第一个出栈的元素删掉，让下一个元素做第一个元素
}
}
return !stack.length//通过判断stack中还有没有元素来判断是否全部出栈
};

使括号有效的最少添加

原题链接点这去练手
只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。

例如，如果 s = “()))” ，你可以插入一个开始括号为 “(()))” 或结束括号为 “())))” 。
返回为使结果字符串 s 有效而必须添加的最少括号数。

示例 1：

输入：s = "())"
输出：1
示例 2：

输入：s = "((("
输出：3

提示：

1 <= s.length <= 1000
s 只包含 '(' 和 ')' 字符。

思路：

和上面的有效的括号一题是不是很像，就是添多少可以全部配对。代码都差不多，一样的判断把配对的可以出栈去了不管，要添加的括号数就是栈中剩下的没配对的

AC代码（js）

/**
 * @param {string} s
 * @return {number}
 */
var minAddToMakeValid = function(s) {
if(!s.length){
return 0;

}
let stack=[];
for(let i=0;i<s.length;i++){
    //一定不能反过来，因为要想凑对，应该是新栈里的是左括号，不然就一直不能凑对
if(s[i]===')'&&stack[stack.length-1]==='(')stack.pop();//配上了就出栈
else stack.push(s[i]);//不满足就入栈
}
return stack.length;//剩余元素个数即所求
};

股票价格跨度

原题链接点这去练手
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用  10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。

思路：

一个栈用来放价格，一个栈用来放日期，他们是一一对应的，日期从0开始；对每一个接收的价格（看作今天），从今天开始往前比之前每天的价格，但注意是要求连续的不高于今天的价格，那就把符合题意的日期出栈，直到遇到第一个不符合的日期，停止比较，跳出来不比了；怎么计算跨度呢？用今天的日期减第一个不符合的日期就是结果（包括今天在内），还有一种特殊情况，今天之前的日期都符合题意，那栈都出完了，为空了，那就直接等于今天的日期，也等于当前价格栈的长度

AC代码（js语言）

var StockSpanner = function() {
this.stock=[];//一个栈用来放日期，从0开始
// this.stock.push(0);
this.priceStock=[];//一个栈用来放价格

};

/** 
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {
//把价格放进去
this.priceStock.push(price);//入栈

//判断,日期栈不为空并且其栈顶日期对应的价格不高于今天的价格，就把这个日期出栈,直到栈顶日期的价格大于今天的价格

var res=0;
/**这里注意哦，[this.stock.length-1]是栈顶元素下标，this.stock[this.stock.length-1]是栈顶元素（日期），
this.priceStock[this.stock[this.stock.length-1]]是这个日期对应的价格
*/
while(this.stock.length&&price>=this.priceStock[this.stock[this.stock.length-1]]){
this.stock.pop();//出栈
}

 //栈为空，就是说今天及今天之前的都符合题意
if(!this.stock.length){
res=this.priceStock.length;
}else{
//对日期栈操作完后，要判断跨度，其实就是今天的日期减去日期栈顶的日期
res=this.priceStock.length-1-this.stock[this.stock.length-1];
}
this.stock.push(this.priceStock.length-1);
return res;


};