JS刷题之路-栈

⭐️最近一直在刷题，所以鸽了，这不我快马加鞭赶出了栈相关的JS题；题不在多，掌握了思维就会发现万变不离其宗（其实我觉着和刷数学题是差不多的感觉哈哈）

思维导图

获取高清PDF，请在微信公众号【小狮子前端】回复【LeetCode】，一起刷题或者交流学习可以加Q群【666151691】

上述刷题路径呢是前辈【一百个Chocolate】总结的，我个人觉得按照这样在LeetCode上刷题挺好的；在这一篇呢只讲栈，后续持续加更，等我刷完差不多就总结完了~

来，第一题搞个开胃小菜，往后逐渐加大力度

LeetCode-栈

一、20.有效的括号

题目链接：20.有效的括号

题目描述

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

有效字符串需满足：

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

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

解题思路

处在后面的左括号要最先匹配到对应的右括号，用栈的后进先出的思想，后进匹配弹出，接着匹配下一左括号；

代码如下（示例）：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    if (s.length & 1) return false; //奇数肯定是false，直接返回节省时间
    let stack = [];
    let obj = { //存一个键值对，同理也可以用map存，也可以不存，不存的话就会多几个if匹配语句
        ")": "(",
        "]": "[",
        "}": "{"
    };
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(" || s[i] === '[' || s[i] === "{") { //匹配左括号
            stack.push(s[i]);
        } else if (stack[stack.length - 1] === obj[s[i]]) { //匹配右括号
            stack.pop();
        } else {
            return false;
        }
    }
    return !stack.length;
};

不存的话会快一点，代码也更清晰明了，但如果括号类型多了的话代码就会有点冗余了

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    // 如果是奇数，不可能匹配成功，直接返回false
    if (s.length & 1) 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
    }
    return !stack.length
};

二、946. 验证栈序列

题目链接：946. 验证栈序列
题目描述
给定 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 之前弹出。

提示：

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。

解题思路

借助一个新栈来存放从pushed加入栈的元素，然后每次和popped的元素进行比对，如果匹配成功出栈，如果这个新栈为空，那么代表这个栈入栈和出栈序列是合理的，返回 true，否则返回false；

这题比上一题难一丢丢，但还是挺简单的吧，我就不画栈图了，简单的示意，聪明的你肯定能明白的~

代码如下（示例）：

/**题解：
 * stack      popped
 * 1          4
 * 12         4 
 * 123        4
 * 1234       4   相等弹出 popped下标++    
 *   123      5
 * 1235       5   相等弹出 popped下标++
 *   123      3
 *   12       2
 *   1        1
 * 栈空
 */

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function (pushed, popped) {
    var stack = [];
    var j=0;//索引
    for (let cur of pushed) {
        stack.push(cur); //存
        while (stack[stack.length - 1] === popped[j] && stack.length > 0) { //匹配弹出
            stack.pop();
            j++;
        }
    }
    return !stack.length;
};

三、921.使括号有效的最少添加

题目链接：921.使括号有效的最少添加
题目描述
给定一个由 ‘(‘ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(‘ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。

从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：

输入："())"
输出：1

示例 2：

输入："((("
输出：3

示例 3：

输入："()"
输出：0

示例 4：

输入："()))(("
输出：4

提示：

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

解题思路

分析示例4 ：输入："()))((" 输出：4
第一个左括号匹配到第一个右括号

接下来的两个没办法匹配到左括号（栈为空）于是加入栈中（虽然说它也没机会被匹配到了）

接下来遇到两个左括号同样的道理加入栈中。

可以用很多方法来存括号，但是用栈做更方便，这里用栈来做，匹配弹出，剩下不匹配的长度就是我们要加的括号

代码如下（示例）：

/**
 * @param {string} S
 * @return {number}
 */
var minAddToMakeValid = function (S) {
    let stack = [];
    for(let cur of S){
        if(cur === ')' && stack[stack.length-1] === '('){//当前值为右括号且栈顶为左括号则弹出
            stack.pop();
        }else{
            stack.push(cur);//否则加入
        }
    }
    return stack.length;
};

前置知识（四五题的）

首先什么是单调栈

顾名思义单调栈就是维护一个单调递减或递增的栈；

单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

如果记不住，或者容易搞混，栈底大就是递增，栈底小就是递减会好记一些

如何使用单调栈

举例单调递增栈：
例如，栈中自顶向下的元素为 10,20,30,40,50 ，插入元素 25 时为了保证单调性需要依次弹出元素，操作后栈变为 25,30,40,50 。

伪代码：

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

什么题适合用单调栈来做呢？

总结可能不会太全面，清谅解：

求最长的单调上升、递减区间
针对每个数，寻找它和它左 / 右边第一个比它大 / 小的数的值，以及相距多少个数。
左右配对
多个区间中的最值 / 某个数为最值的最长区间
有了这些前置知识我们再来看看这道题

四、901. 股票价格跨度

题目链接：901. 股票价格跨度
题目描述
编写一个 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%。

解题思路

题意关键：求价格小于或等于今天价格的最大连续日数（往前数）
这道题非常适合用单调栈来做，以题目 [100, 80, 60, 70, 60, 75, 85]为例，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

用两个栈一个用来存价格，一个用来存跨度；
维护一个单调递增的栈，大的加进来，小的弹出去；
分析过程：
首先栈为空，加入100，w初始为1

下一个值，80，栈顶值不是小于等于它，于是加入，w初始为1入栈，同理60也是

下一个值：70，此时栈中[100,80,60],大于栈顶60，将栈顶元素弹出，并计算w，w=初始1+w(60)=1+1=2加入w栈，其中w（60）其实就是栈顶的w（因为是同步的）

下一个值：60，与80的原理

下一个值：75，此时栈中[100,80,70,60]，计算w，为1+w(60)+w(70)=1+1+2=4，加入跨度栈w

下一个值：85，w=1+w(75)+w(80)=1+4+1=6 结束

代码如下（示例）：

var StockSpanner = function() {
    this.prices=[];//存价格
    this.weights=[];//存跨度
};

/** 
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {
    let w = 1;//初始
    //当prices栈不为空 且 栈顶小于输入价格  -> 维护单调栈（弹出小于价格的并累加W）
    //以[100, 80, 60, 70, 60, 75, 85]为例，单调栈如下：
    //100           w=1  
    //100,80        w=1   lala
    //100,80,60     w=1
    //100,80,70     w=2  1+1
    //100,80,70,60  w=1  
    //100,80,75     w=4  1+1+2
    //100,85        w=6  1+4+1
    while(this.prices.length>0 && this.prices[this.prices.length-1] <=price){
        this.prices.pop();
        w+=this.weights.pop();
    }
    this.prices.push(price);
    this.weights.push(w);
    return w;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * var obj = new StockSpanner()
 * var param_1 = obj.next(price)
 */

五、739. 每日温度

题目链接：739. 每日温度
题目描述
请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

题目关键在于：求解要想观测到更高的气温，至少需要等待的天数。后续没有温度更高结果为0。

以[73, 74, 75, 71, 69, 72, 76, 73]为例：

第一天73：栈为空将73的下标加入栈中;

第二天74： 74大于栈顶元素值，73弹出，73的结果res[0]值为74的下标减去73的下标，res[0]=1-0=1;

第三天75： 75大于栈顶元素74，74弹出，同理res[1]=2-1=1，栈空75加入；

第四天71，第五天69：小于栈顶加入栈，此时栈：[2（75）,3（71）,4（69）]栈存的下标;

第六天72：大于栈顶元素值，69先弹出，69的结果res[4]值为72的下标减去69的下标，res[4]=5-4=1;循环73还大于现栈顶元素71，71先弹出，71的结果res[3]值为72的下标减去71的下标，res[3]=5-3=2；小于栈顶75，将72加入栈中，此时栈[2（75），5（72）];

第七天76：同上述步骤72 res[5]=6-5=1, 75 res[2]=6-2=4 栈为[76];

第八天73：小于栈顶加入栈中

代码如下（示例）：

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function (T) {
    //[73, 74, 75, 71, 69, 72, 76, 73]
    //74(1)           73->1-0=1
    //75              74->2-1=1
    //75,72(71,69)    69->5-4=1  71->5-3=2
    //76              72->6-5=1  75->6-2=4
    //76,73
    let stack = [];
    var res = new Array(T.length).fill(0); //运用fill方法为数组填0
    for (let i = 0; i < T.length; i++) {
        while (stack.length && T[i] > T[stack[stack.length - 1]]) { //循环条件当前值大于栈顶元素值（栈中存的是下标值）
            number[stack[stack.length - 1]] = i - stack.pop(); //弹出栈的元素的跨度等于当前值下标减去弹出（栈顶）下标  
        }
        stack.push(i);
    }
    return res;
};

六、907. 子数组的最小值之和

题目链接：907. 子数组的最小值之和
题目描述

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

由于答案可能很大，因此返回答案模 10^9 + 7。

示例：

输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

提示：

1 <= A <= 30000
1 <= A[i] <= 30000

解题思路

关键在于：求子数组中最小值的和，就是求以 A[i] 作为最小数能构成的数组有多少个。

以[3,1,2,4]为例 ,以1 为最小数，能构成的数组数为 (1+1)*(2+1) ，左边3比它大，右边2、4比它大。

用单调栈求出 arr[i] 对应的左（右）最近比 arr[i] 小的数的索引 leftStack（rightStack），arr[i] 为最小数能形成的数组的个数为：leftStack[i]*rightStack[i]

知道个数再乘以值累加，得到结果；

代码如下（示例）：

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumSubarrayMins = function (arr) {
    let mod = 1e9 + 7;
    let stack = [];
    let leftStack = [];
    for (let i = 0; i < arr.length; i++) {
        while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) { //左边设置大于等于了，右边就只能是大于了，不然会重复计算
            stack.pop();
        }
        // 如果栈为空，即左边都比自己大，则返回i+1，否则返回i减栈顶元素（栈保存下标值）
        leftStack[i] = stack.length ? i - stack[stack.length - 1] : i + 1
        stack.push(i);
    }
    stack = [];
    let rightStack = [];
    for (let i = arr.length - 1; i >= 0; i--) {
        while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        // 如果栈为空，即右边都比自己大，则返回arr.length-i，否则返回栈顶元素（即保存的下标值）-i
        rightStack[i] = stack.length ? stack[stack.length - 1] - i : arr.length - i
        stack.push(i);
    }
    let res = 0;
    for (let i = 0; i < arr.length; i++) {
        // 以arr[i] 为最小值的子数组的组合共有leftStack[i]*rightStack[i]种情况，那么和的话乘以arr[i]累加即可
        res += (leftStack[i] * rightStack[i] * arr[i]);
        res %= mod;
    }
    return res;
};

七、1190. 反转每对括号间的子串

题目链接：1190. 反转每对括号间的子串
题目描述
给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中不应包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"

示例 2：

输入：s = "(u(love)i)"
输出："iloveu"

示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"

示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

提示：

0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的

解题思路

题目关键：括号内到外，逐层反转每对匹配括号中的字符串，理解到底是怎么匹配的
提示中关键：括号都是成对的

以示例 3：s = “(ed(et(oc))el)”为例，为了更清楚直观，我写一下下标：

示例：
(    e    d    (    e    t    (    o    c    )    )   e   l    )
0    1    2    3    4    5    6    7    8    9   10   11  12  13

pair://左右括号一一对应
13   10   9   
0    3    6

首先用一个for循环和栈，将左右配对的括号存起来

第一个遇到的左括号0：0->13找到右括号，逆序 i- -输出12 11（l e），直到遇到下一个括号10；

第二个遇到的右括号10:10->3，i++输出 4 5（et），遇到6；

第三个遇到括号6：6->9，i- -，8 7 （c o),遇到6；

第四个遇到括号6：6->9，i++，遇到10；

第五个遇到括号10：10->3，i- -，2 1 （d e),遇到0；

第六个遇到括号0：0->13，i++，13>len 结束；

输出：”leetcode”

i++和i–可以用一个参数储存方向，遇到括号就匹配反向；

代码如下（示例）：

/**
 * @param {string} s
 * @return {string}
 */

/**
 * 0->13    12 11  10  le
 * 10->3    4 5    6   et
 * 6->9     8 7    10  co
 * 10->3    2 1    0   de
 * 0->13    14     (end)
 */
var reverseParentheses = function (s) {
    let pair = [];
    let stack = [];
    //匹配括号
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i)
        } else if (s[i] === ')') {
            let j = stack.pop();
            pair[i] = j; //相当于键值存储，a[0]=13,a[13]=0
            pair[j] = i;
        }
    }
    let res = [],
        r = 0;
    //
    for (let i = 0, direction = 1; i < s.length; i += direction) {//i=i+direction反转方向  i++或i--
        if (s[i] === '(' || s[i] === ')') {
            i = pair[i]; //找匹配的括号并修改i的下标为匹配括号下标 0->13  i=13
            direction = -direction; //反向
        } else {
            res[r] = s[i];
            r++;
        }
    }
    return res.join(''); //去逗号
};

如果上个方法没看懂？再说一个的方法吧

第二种解题思路

初始化栈，栈顶元素为 “ “ 遇到 ‘(‘: 向栈顶压入空字符串遇到 ‘)’: 把栈顶的最后一个元素翻转 + 栈顶倒数第二个元素遇到字符: 直接将栈顶最后一个元素与它拼上

参考tuotuoli 大佬解题思路

样例栈数组操作示意：

样例：a(bcdefghijkl(mno)p)q

a ['a']
( ['a', '']
b ['a', 'b']
c ['a', 'bc']
d ['a', 'bcd']
e ['a', 'bcde']
f ['a', 'bcdef']
g ['a', 'bcdefg']
h ['a', 'bcdefgh']
i ['a', 'bcdefghi']
j ['a', 'bcdefghij']
k ['a', 'bcdefghijk']
l ['a', 'bcdefghijkl']
( ['a', 'bcdefghijkl', '']
m ['a', 'bcdefghijkl', 'm']
n ['a', 'bcdefghijkl', 'mn']
o ['a', 'bcdefghijkl', 'mno']
) ['a', 'bcdefghijklonm']
p ['a', 'bcdefghijklonmp']
) ['apmnolkjihgfedcb']
q ['apmnolkjihgfedcbq']

代码如下（示例）：

/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function(s) {
  let stack = ['']
  for(let i=0;i<s.length;i++){
    let ch = s[i]
    if(ch === '('){
      stack.push('')
    }else if(ch === ')'){
      let str = stack.pop()
      let tmp = str.split('').reverse().join('')
      stack[stack.length-1] += tmp
    }else{
      stack[stack.length-1] += ch
    }
  }
  return stack.pop()
};

最后一道简单题：

八、1249.移除无效的括号

题目链接：1249.移除无效的括号

题目描述

给你一个由 ‘(‘、’)’ 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 ‘(‘ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下任意一条要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：

输入：s = "lee(t(c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2：

输入：s = "a)b(c)d"
输出："ab(c)d"

示例 3：

输入：s = "))(("
输出：""
解释：空字符串也是有效的

示例 4：

输入：s = "(a(b(c)d)"
输出："a(b(c)d)"

提示：

1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小写字母

解题思路

解题关键：匹配到的括号保留，没匹配删除

代码如下（示例）：

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function (s) {
    let res = [...s];
    //栈匹配括号，剩下括号删除
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else if (s[i] === ')') {
            if (stack.length > 0) {
                stack.pop();
            } else {
                delete(res[i]); //栈为空，没有左括号，把当前右括号删除
            }
        }
    }
    while (stack.length) { //删除栈顶元素直到栈空
        delete(res[stack.pop()]);
    }
    return res.join('');
};