LeetCode 栈章节

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

bool isValid(string s) {
    if (s.size() % 2 == 1)
        return false;
    unordered_map<char, char> hash = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };
    string st;
    for (char ch : s) {
        if (hash.count(ch)) { // ) ] }
            if (!st.empty() && hash[ch] == st.back())
                st.pop_back();
            else
                return false;
        } else { // ( [ {
            st.push_back(ch);
        }
    }
    return st.empty();
}

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

进阶：

• 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

利用栈的思想，构建字符串

string build(string str) {
    string s;
    for (char ch : str) {
        if (ch == '#') {
            if (s.size() > 0)
                s.pop_back();
        } else {
            s.push_back(ch);
        }
    }
    return s;
}

bool backspaceCompare(string s, string t) {
    return build(s) == build(t);
}

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= s.length <= 10^5
2. s 仅由小写英文字母组成。

从左向右顺次处理字符串，利用back， pop_back 和push_back函数来模拟栈的后入先出。

string removeDuplicates(string s) {
    string ans;
    for (char ch : s) {
        if (!ans.empty() && ans.back() == ch)
            ans.pop_back();
        else
            ans.push_back(ch);
    }
    return ans;
}

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["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.

提示：

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 10^4 次

一个普通栈用于存储元素，另一个辅助栈用于记录每一步操作后栈内的最小元素。

stack<int> st;
stack<int> min_st;

MinStack() {
    min_st.push(INT_MAX);
}

void push(int val) {
    st.push(val);
    min_st.push(min(min_st.top(), val));
}

void pop() {
    st.pop();
    min_st.pop();
}

int top() {
    return st.top();
}

int getMin() {
    return min_st.top();
}

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。

**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

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

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

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

提示：

• 1 <= s.length <= 3 * 105
• s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
• s 表示一个 有效表达式
• 表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
• 题目数据保证答案是一个 32-bit 整数

• 加号：将数字压入栈；减号：将数字的相反数压入栈；

• 乘除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果

int calculate(string s) {
    vector<int> st;
    int n = s.size();
    int num = 0;
    char preSign = '+'; // 记录上一个运算符
    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) {
            // 一个数字结束 或 最后一个数字
            switch (preSign) {
            case '+':
                st.push_back(num);
                break;
            case '-':
                st.push_back(-num);
                break;
            case '*':
                st.back() *= num;
                break;
            case '/':
                st.back() /= num;
                break;
            }
            preSign = s[i];
            num = 0;
        }
    }
    return accumulate(st.begin(), st.end(), 0);
}

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

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

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

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

• 数字：提取出这个数字，放入“数字栈”中。

• ‘[’：将空串放入“字符串栈”中

• ‘]’：记录重复后的栈顶元素，出栈，再添加到“字符串栈”栈顶的字符串后面。

• 单独的字符：提取出这个字符，添加到“字符串栈”栈顶的字符串后面。

string decodeString(string s) {
    vector<int> v;    // 数字栈
    stack<string> st; // 字符串栈
    st.push("");
    for (int j = 0; j < s.size(); ++j) {
        if (isdigit(s[j])) { // 放入“数字栈”中
            if (j == 0 || !isdigit(s[j - 1]))
                v.push_back(s[j] - '0');
            else
                v.back() = v.back() * 10 + (s[j] - '0');
        } else if (s[j] == '[') { // 将空串放入“字符串栈”中
            st.push("");
        } else if (s[j] == ']') { // 将栈顶元素重复之后，放入“字符串栈”中
            string tmp;
            for (int i = 0; i < v.back(); ++i)
                tmp += st.top();
            v.pop_back();
            st.pop();
            st.top() += tmp;
        } else {  // 将字符串放入“字符串栈”中
            st.top() += s[j];
        }
    }
    string ans;
    while (!st.empty()) {
        ans = st.top() + ans;
        st.pop();
    }
    return ans;
}

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

示例 1:

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

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

单调栈：单调栈是一种特殊的数据结构，栈内的元素按照一定的顺序排列。

通过栈来单调递减地存储温度。如果有大于栈顶的温度出现时，满足题意更新ans数组即可；如果有小于栈顶的温度出现时，将下标入栈，等待后续有更高的温度出现再出栈即可。

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ans(n, 0);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int index = st.top();
            ans[index] = i - index;
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

利用单调栈来高效地找出每个柱子左右两侧第一个高度小于它的柱子位置，用于计算矩形面积。

确定以i位置高度可以形成矩形的左边界：

• 当栈不为空且栈顶柱子的高度大于等于当前柱子的高度时，不断弹出栈顶元素。因为栈顶柱子的高度大于等于当前柱子时，它不是当前柱子左侧第一个高度小于它的柱子，直到栈顶柱子的高度小于当前柱子。
• 如果栈为空，说明当前柱子左侧没有高度小于它的柱子，将 left[i] 设为 0；否则，将 left[i] 设为栈顶元素的索引 + 1。

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st; // 单增队列
    vector<int> left(n), right(n);
    // 确定以i位置高度可以形成矩形的左边界
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && heights[st.top()] >= heights[i])
            st.pop();
        left[i] = (st.empty() ? 0 : st.top() + 1);
        st.push(i);
    }
    // 确定以i位置高度可以形成矩形的右边界
    st = stack<int>();
    for (int i = n - 1; i >= 0; --i) {
        while(!st.empty() && heights[st.top()] >= heights[i])
            st.pop();
        right[i] = (st.empty() ? n - 1 : st.top() - 1);
        st.push(i);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, (right[i] - left[i] + 1) * heights[i]);
    }
    return ans;
}