• 通关算法题之 ⌈栈和队列⌋

    栈和队列

    155. 最小栈

    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

    实现 MinStack 类:

    • MinStack() 初始化堆栈对象。
    • void push(int val) 将元素val推入堆栈。
    • void pop() 删除堆栈顶部的元素。
    • int top() 获取堆栈顶部的元素。
    • int getMin() 获取堆栈中的最小元素。
    输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    使用两个栈，一个正常的按照栈的逻辑进行压入和弹出操作，另一个存储最小值。

    • 存储最小值的栈配合另一个栈，在压入时候，若压入的值小于等于最小值栈的栈顶元素，则也将该值压入到最小值栈，来保持最小值栈的栈顶一直是当前可以获得的最小值；
    • 在弹出的时候，判断最小值栈和另一栈是否具有相同的栈顶值，若相同，则最小值栈顶元素也弹出，保证最小值栈的栈顶元素一直是另一个栈中的最小值；
    • 返回栈顶元素，则直接返回正常的栈的顶端元素；返回最小值元素，则直接返回最小值栈的栈顶元素。
    class MinStack {
public:
    MinStack() {}
    
    stack<int> st;
    stack<int> minSt;

    void push(int val) {
        st.push(val);
        if(minSt.empty() || val <= minSt.top()){
            minSt.push(val);
        }
    }
    
    void pop() {
        if(st.top() == minSt.top()){
            minSt.pop();
        }
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.top();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    225. 用队列实现栈

    请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

    实现 MyStack 类：

    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

    注意：

    • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
    • 你所使用的语言也许不支持队列， 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
    输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

    class MyStack {
public:
    queue<int> que;

    MyStack() {}
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int n = que.size() - 1;
        for(int i = 0; i < n; i++){
            que.push(que.front());
            que.pop();
        }
        int res = que.front();
        que.pop();
        return res;
    }
    
    int top() {
        return que.back();
    }
    
    bool empty() {
        return que.empty();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    232. 用栈实现队列

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

    实现 MyQueue 类：

    • void push(int x) 将元素 x 推到队列的末尾
    • int pop() 从队列的开头移除并返回元素
    • int peek() 返回队列开头的元素
    • boolean empty() 如果队列为空，返回 true ；否则，返回 false

    说明：

    • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    使用两个栈 s1, s2 就能实现一个队列的功能。当调用 push 让元素入队时，只要把元素压入 s1 即可：

    image-20220716150056532

    使用 peek 或 pop 操作队头的元素时，若 s2 为空，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了：

    image-20220716150313819 
    class MyQueue {
public:
    stack<int> st1;
    stack<int> st2;

    MyQueue() {

    }
    
    void push(int x) {
        st1.push(x);
    }
    
    int pop() {
        peek(); // 先调用 peek 保证 st2 非空
        int res = st2.top();
        st2.pop();
        return res;
    }
    
    int peek() {
        if(st2.empty()){
            // 把 s1 元素压入 s2
            while(!st1.empty()){
                st2.push(st1.top());
                st1.pop();
            }
        }
        return st2.top();
        
    }
    
    bool empty() {
        return st1.empty() && st2.empty();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    946. 验证栈序列

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

    输入：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

    • 1
    • 2
    • 3
    • 4
    • 5

    模仿压栈和出栈的动作。

    class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size() != popped.size()){
            return false;
        }
        stack<int> st;
        int j = 0; // 注意是
        for(int i = 0; i < pushed.size(); i++){
            // 入栈
            st.push(pushed[i]);
            // 能出栈，则尽量出栈
            while(j < popped.size() && !st.empty() && st.top() == popped[j]){
                st.pop();
                j++;
            }
        }
        //若栈为空，则说明满足要求
        return st.empty();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    20. 有效的括号

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

    有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。
    输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false

    • 1
    • 2
    • 3
    • 4

    括号匹配是使用栈解决的经典问题，有以下三种情况：

    1. 字符串里左方向的括号多余了 ，所以不匹配。
    括号匹配1
    1. 括号没有多余，但是括号的类型没有匹配上。
    括号匹配2
    1. 字符串里右方向的括号多余了，所以不匹配。
    括号匹配3

    • 第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false；

    • 第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符，所以return false；

    • 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false；

    那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

    class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(char ch : s){
            if(ch == '('){
                st.push(')');
            }else if(ch == '{'){
                st.push('}');
            }else if(ch == '['){
                st.push(']');
            }else if(st.empty() || ch != st.top()){
                // 第二、三种情况
                return false;
            }else if(ch == st.top()){
                // st.top() 与 s[i]相等，栈弹出元素
                st.pop();
            }
        }
        // 第一种情况
        return st.empty();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

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

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

    • 它是一个空字符串，或者
    • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
    • 它可以被写作 (A)，其中 A 是有效字符串。

    给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。

    • 例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

    返回为使结果字符串 s 有效而必须添加的最少括号数。

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

    • 1
    • 2
    • 3
    • 4

    转换思路，改为求删除最少的字符数量，使得原字符串有效。

    class Solution{
public:
    int minAddToMakeValid(string s){
        int left = 0; //统计当前的左括号的数量
        int res = 0;  //统计需要删除的数量
        for (char &ch : s){
            if (ch == '('){ //增加左括号
                left++;
            }else{
                if (left == 0){ //不能配对，需要删除
                    res++;
                }else{          //和右括号配对成功，减去一个左括号
                    left--;
                }
            }
        }
        return res + left; //返回需要删除的数量
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    或者：

    class Solution{
public:
    int minAddToMakeValid(string s){
        // res 记录插入次数
        int res = 0;
        // need 变量记录右括号的需求量
        int need = 0;
        for(char& ch : s){
            if(ch == '('){
                need++;
            }else{
                need--;
                if(need == -1){
                    need = 0;
                    // 需插入一个左括号
                    res++;
                }
            }
        }
        return res + need;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    1541. 平衡括号字符串的最少插入次数

    给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

    • 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
    • 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

    比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。你可以在任意位置插入字符 ‘(’ 和 ‘)’ 使字符串平衡，请你返回让 s 平衡的最少插入次数。

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

    • 1
    • 2

    和上题类似：

    class Solution {
public:
    int minInsertions(string s) {
        // res 记录插入次数
        // need 记录需右括号的需求量
        int res = 0, need = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                need += 2;
                if (need % 2 == 1) {
                    // 插入一个右括号
                    res++;
                    // 对右括号的需求减一
                    need--;
                }
            }else{
                need--;
                // 右括号太多
                if (need == -1) {
                    // 插入一个左括号
                    res++;
                    // 对右括号的需求变为 1
                    need = 1;
                }
            }
        }
        return res + need;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    1047. 删除字符串中的所有相邻重复项

    给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

    输入："abbaca"
输出："ca"

    • 1
    • 2

    对当前字符来说，如果结果字符串是空的，则直接将当前字符压入到结果字符串中；如果结果字符串不为空，则和结果字符串的尾部字符比较，若相同，则将尾部字符弹出，若不相同，则将当前字符压入到结果字符中。

    class Solution {
public:
    string removeDuplicates(string s) {
        string res;
        for(char ch : s){
            if(res.empty() || res.back() != ch){
                res += ch;
            }else{
                res.pop_back();
            }
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    150. 逆波兰表达式求值

    根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

    注意：两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

    输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

    • 1
    • 2
    • 3

    逆波兰表达式发明出来就是为了方便计算机运用「栈」进行表达式运算的，其运算规则是，按顺序遍历逆波兰表达式中的字符

    • 如果是数字，则放入栈；

    • 如果是运算符，则将栈顶的两个元素拿出来进行运算，再将结果放入栈。

    对于减法和除法，运算顺序别搞反了，栈顶第二个数是被除（减）数。

    class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(string& token : tokens){
            if(token == "+" || token == "-" || token == "*" || token == "/"){
                int a = st.top();st.pop();
                int b = st.top();st.pop();
                if(token == "+") st.push(a + b);
                if(token == "-") st.push(b - a);
                if(token == "*") st.push(a * b);
                if(token == "/") st.push(b / a);
            }else{
                st.push(stoi(token));
            }
        }
        return st.top();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    224. 基本计算器

    给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。注意: 不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

    输入：s = "1 + 1"
输出：2
输入：s = " 2-1 + 2 "
输出：3
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        st.push(1);
        // sign为1或者-1，表示数字的正负
        int sign = 1, res = 0, i = 0;
        int n = s.size();
        while (i < n) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '+') {//若为+则sign为1
                sign = st.top();
                i++;
            } else if (s[i] == '-') {//若为-则sign为-1
                sign = -st.top();
                i++;
            } else if (s[i] == '(') {//若为(则sign入栈
                st.push(sign);
                i++;
            } else if (s[i] == ')') {//若为)则sign出栈
                st.pop();
                i++;
            } else {//若为0-9则将字符串转为整形num，更新res
                long num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                res += sign * num;
            }
        }
        return res;
    }
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    227. 基本计算器 II

    给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值，整数除法仅保留整数部分。**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

    输入：s = "3+2*2"
输出：7
输入：s = " 3/2 "
输出：1
输入：s = " 3+5 / 2 "
输出：5

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        char sign = '+';
        int num = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                if(sign == '+') st.push(num);
                if(sign == '-') st.push(-num);
                if(sign == '*') st.top() *= num;
                if(sign == '/') st.top() /= num;
                sign = s[i];
                num = 0;
            }
        }
        int res = 0;
        while(!st.empty()){
            res += st.top();
            st.pop();
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    772. 基本计算器 III

    实现一个基本的计算器来计算简单的表达式字符串。表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) ，整数除法需要向下截断 。

    输入：s = "1+1"
输出：2
输入：s = "6-4/2"
输出：4
输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21
输入：s = "(2+6*3+5-(3*14/7+2)*5)+3"
输出：-12


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    class Solution {
public:
    int calculate(string s) {
        stack<int> st;
        char sign = '+';
        int num = 0;
        int n = s.size();
        for (int i = 0; i < n - 1; ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + int(s[i] - '0');
            }
            if(s[i] == '('){
                //s的子串，找)，剔除()
                int count = 0;
                for(int j = i; j < n; j++){
                    if(s[j] == '(') count++;
                    if(s[j] == ')') {
                        count--;
                        if(count == 0) break;
                    }
                }
                num = calculate(s.substr(i + 1, j - i - 1));
                i = j + 1;
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                switch (sign) {
                    case '+':
                        st.push(num);
                        break;
                    case '-':
                        st.push(-num);
                        break;
                    case '*':
                        st.top() *= num;
                        break;
                    case '/':
                        st.top() /= num;
                }
                sign = s[i];
                num = 0;
            }
        }
        int res = 0;
        while(!st.empty()){
            res += st.top();
            st.pop();
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    394. 字符串解码

    给定一个经过编码的字符串，返回它解码后的字符串。

    编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

    输入：s = "3[a]2[bc]"
输出："aaabcbc"
输入：s = "3[a2[c]]"
输出："accaccacc"

    • 1
    • 2
    • 3
    • 4

    使用栈来解压中括号中的内容：

    1. 一个栈用于存储字符串，一个栈用于存储数字；
    2. 根据遇到的中括号的左括号或右括号，执行不同的操作；
    3. 遇到左括号，就把当前解析出来的内容压入到对应的两个栈中；
    4. 遇到右括号，就把之前的字符串和数字拿出来进行解压，既去除当前左括号对应的字符串的压缩；
    class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> strs;
        int num = 0;
        string str;
        for(char ch : s){
            if(isdigit(ch)){
                num = num * 10 + (ch - '0');
            }else if(isalpha(ch)){
                str += ch;
            }else if(ch == '['){
                nums.push(num);
                num = 0;
                strs.push(str);
                str = "";
            }else if(ch == ']'){
                int n = nums.top();
                nums.pop();
                for(int i = 0; i < n; i++){
                    strs.top() += str;
                }
                str = strs.top();
                strs.pop();
            }
        }
        return str;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    239. 滑动窗口最大值（难）

    给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

    输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    单调栈

    496. 下一个更大元素 I

    nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

    对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

    输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    单调栈的模板：

    输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

    比如说，输入一个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

    vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(nums.size());
	stack<int> st;
    for (int i = n - 1; i >= 0; i--) { // 倒着往栈里放
        while (!st.empty() && st.top() <= nums[i]) {
            st.pop();
        }
        res[i] = st.empty() ? -1 : st.top();
        st.push(nums[i]);
    }
    return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    本题答案：

    class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> st;
        for(int i = nums2.size() - 1; i >= 0; i--){
            int num = nums2[i];
            while(!st.empty() && st.top() <= num){
                st.pop();
            }
            map[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        vector<int> res;
        for(int num : nums1){
            res.push_back(map[num]);
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    739. 每日温度

    给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

    输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

    • 1
    • 2

    这个问题本质上也是找下一个更大元素，只不过现在不是问你下一个更大元素的值是多少，而是问你当前元素距离下一个更大元素的索引距离而已。

    class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n);
        stack<int> st;
        for(int i = n - 1; i >= 0; i--){
            while(!st.empty() && temperatures[i] >= temperatures[st.top()]){
                st.pop();
            }
            res[i] = st.empty() ? 0 : st.top() - i;
            st.push(i);
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    503. 下一个更大元素 II

    给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

    输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

    • 1
    • 2
    • 3

    比如输入是 [2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为下一个更大元素？

    思路：将数组长度翻倍，索引用 % 运算符求模（余数）。

    class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        stack<int> st;
        for(int i = n * 2 - 1; i >= 0; i--){
            int num = nums[i % n];
            while(!st.empty() && st.top() <= num){
                st.pop();
            }
            res[i % n] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    402. 移掉 K 位数字

    给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

    输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    主要思路：

    1. 使用单调栈的思想，去除k个字符；
    2. 先按照单调升的顺序，去除部分元素（可能全部的k个）；
    3. 注意对前导 0 的处理；
    4. 对最后的字符进行可能的剩余字符的删除；
    class Solution {
public:
    string removeKdigits(string num, int k) {
        string res;
        for(char ch : num){
            // 维护单调栈的上升顺序
            while(!res.empty() && k && ch < res.back()){
                res.pop_back();
                k--;
            }
            // 处理前导零
            if(res.empty() && ch == '0'){
                continue;
            }
            res += ch;
        }
        // 处理剩余的元素
        while(k && !res.empty()){
            res.pop_back();
            k--;
        }
        return res.empty() ? "0" : res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
  • 相关阅读:
    centos7中卸载Java、jdk命令
    redis 集群（cluster）
    从0开始学习JavaScript--JavaScript基础
    移远EC600U-CN开发板 11.17
    Java数据结构与算法(爬楼梯动态规划)
    【小想法】第1期：模型工程化，向量相似度，早停机制，BERT微调小trick
    vue3-项目快速搭建和初始化
    linux 中 mq_notify 创建线程监控消息队列实现原理
    QSS编辑器QssEditor之二：加载有变量的QSS
    seaborn
  • 原文地址：https://blog.csdn.net/weixin_42461320/article/details/128199726