Hexo

LeetCode-Hot100-栈

  • ~4.26K 字
  1. 1. 20. 有效的括号 C++
  2. 2. 155.最小栈 C++

20. 有效的括号 C++

写法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    unordered_map<char, char> mp = {{')', '('}, {']', '['}, {'}', '{'}};
public:
    bool isValid(string s) {
        if (s.length() % 2) { // s 长度必须是偶数
            return false;
        }
        stack<char> st;
        for (char c : s) {
            // mp.contains(c) 用来判断 c 是不是 mp 的一个 key
            if (!mp.contains(c)) { // c 是左括号
                st.push(c); // 入栈
            } else { // c 是右括号
                if (st.empty() || st.top() != mp[c]) {
                    return false; // 没有左括号，或者左括号类型不对
                }
                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
class Solution {
    unordered_map<char, char> mp = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
public:
    bool isValid(string s) {
        if (s.length() % 2) { // s 长度必须是偶数
            return false;
        }
        stack<char> st;
        for (char c : s) {
            if (mp.contains(c)) { // c 是左括号
                st.push(mp[c]); // 入栈对应的右括号
            } else { // c 是右括号
                if (st.empty() || st.top() != c) {
                    return false; // 没有左括号，或者左括号类型不对
                }
                st.pop(); // 出栈
            }
        }
        return st.empty(); // 所有左括号必须匹配完毕
    }
};

写法三

用 if-else 代替 mp 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2) { // s 长度必须是偶数
            return false;
        }
        stack<char> st;
        for (char c : s) {
            if (c == '(') {
                st.push(')'); // 入栈对应的右括号
            } else if (c == '[') {
                st.push(']');
            } else if (c == '{') {
                st.push('}');
            } else { // c 是右括号
                if (st.empty() || st.top() != c) {
                    return false; // 没有左括号，或者左括号类型不对
                }
                st.pop(); // 出栈
            }
        }
        return st.empty(); // 所有左括号必须匹配完毕
    }
};

155.最小栈 C++

前置知识：关于 emplace 和 push
在 C++ 里， stack::emplace 是用来直接在栈顶“原地构造”元素的函数，比 push 更高效。

一、基本作用

  • stack 的成员函数，C++11 起支持
  • 功能：在栈顶直接构造对象，不产生临时对象、不拷贝/移动
  • 用法：把构造函数的参数直接传给 emplace
1
2
3
4
5
6
7
8
9
10
11
#include <stack>
#include <string>
using namespace std;

stack<string> st;

// push：先造临时对象，再拷贝/移动进去
st.push(string("hello"));

// emplace：直接在栈里构造，更高效
st.emplace("hello");

二、和 push 的区别

  • push：传已经建好的对象，可能拷贝/移动
  • emplace：传构造参数，原地构造，少一次拷贝/移动

对 复杂对象（string、自定义类），emplace 明显 更优。

三、自定义类示例

1
2
3
4
5
6
7
8
9
10
11
12
13
struct A {
    int x;
    string s;
    A(int x, string s) : x(x), s(s) {}
};

stack<A> st;

// push：要先构造对象
st.push(A(1, "abc"));

// emplace：直接传构造参数
st.emplace(1, "abc");

四、常用搭配

1
2
3
4
stack<int> st;
st.emplace(10);       // 等价 push(10)
st.top();             // 10
st.pop();

简单记：
能 emplace 就别 push，尤其是存非基本类型时，效率更高、写法也简洁。

本题思路：利用原生栈存数值和最小值，每次新元素入栈同时更新最小值。

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
class MinStack {
    stack<pair<int, int>> st;

public:
    MinStack() {
        // 添加栈底哨兵 INT_MAX
        // 这里的 0 写成任意数都可以，反正用不到
        st.emplace(0,INT_MAX);
    }
    
    void push(int val) {
        st.emplace(val, min(getMin(),val));
    }
    
    void pop() {
        st.pop();
    }
    
    int top() {
        return st.top().first;
    }
    
    int getMin() {
        return st.top().second;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, ,