刷题笔记——栈（C++）

LCR 148. 验证图书取出顺序 - 力扣（LeetCode）

现在图书馆有一堆图书需要放入书架，并且图书馆的书架是一种特殊的数据结构，只能按照 一定 的顺序 放入 和 拿取 书籍。

给定一个表示图书放入顺序的整数序列 putIn，请判断序列 takeOut 是否为按照正确的顺序拿取书籍的操作序列。你可以假设放入书架的所有书籍编号都不相同。

解题思路

模拟+辅助栈。

1° 定义一个栈stk用于存储放入的书籍，再声明一个索引p（初始化为0）记录当前要取出书籍的索引。

2° 遍历putIn数组的每本书籍（i），将每本书籍入栈，查看栈顶元素是否与需要取出的书籍takeOut[p]相同，若相同，则栈顶元素出栈，p指针右移一位，直到栈顶的元素和takeOut[p]不同。

3° 遍历完成后，检查栈是否为空，如果为空则说明所有书籍都按合法的顺序取出，返回 true；否则返回 false。

代码实现

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int> stk;
        int p = 0;
        for(auto& i:putIn){
            stk.push(i);
            while(!stk.empty() && stk.top() == takeOut[p]){
                stk.pop();
                p++;
            }
        }
        return stk.empty();
    }
};

1028. 从先序遍历还原二叉树 - 力扣（LeetCode）

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

解题思路

模拟递归+辅助栈。主要难点在于弄清节点是左子节点还是右子节点。在此之前要明确的是 ：1° 如果节点只有一个子节点，那么保证该子节点为左子节点；2° 从先序遍历还原，遵循“根-左-右”。不妨举例弄清深度和是否为左右子节点的关系：

理清大体的关系后。我们再具体通过辅助栈实现这一操作。

1° 首先，遍历字符串s（索引p）(1)，

    保存每一个节点的值（注意数字连接）(2)，

    以及该节点的深度信息。(3)

2° 创建新节点存储当前遍历到的数值，(4)

    若当前深度 == 栈内元素个数（栈不为空），说明新节点为栈顶元素左子节点；(5)

    若当前深度 < 栈内元素个数，那么循环弹出栈顶元素，(6)

    直到当前深度 == 栈内元素个数，此时新节点为栈顶元素右子节点。(7)

    新节点入栈。(8)

3° 最后若栈内元素 > 1，弹出至只剩一个（剩下的为根节点）(9)。返回即可。(10)

通过实例帮助理解：

代码实现

class Solution {
public:
    TreeNode* recoverFromPreorder(string s) {
        stack<TreeNode*> stk;
        int p = 0;	
        // (1)
        while (p < s.size()) {
            int depth = 0;
            // (3)
            while (s[p] == '-') {
                ++depth;
                ++p;
            }
            // (2)
            int val = 0;
            while (p < s.size() && s[p] != '-') {
                val = val * 10 + (s[p] - '0');
                ++p;
            }
            // (4)
            TreeNode* node = new TreeNode(val);
            // (5)
            if (depth == stk.size()) {
                if (!stk.empty()) {
                    stk.top()->left = node;
                }
            }
            // (6)
            else {
                while (depth < stk.size()) {
                    stk.pop();
                }
                // (7)
                stk.top()->right = node;
            }
            // (8)
            stk.push(node);
        }
        // (9)
        while (stk.size() > 1) {
            stk.pop();
        }
        return stk.top(); (10)
    }
};

下边两道题在之前已有详细解释：

刷题笔记——栈（C）_进击no猪排的技术博客_51CTO博客

以下是C++版实现：

LCR 039. 柱状图中最大的矩形 - 力扣（LeetCode）

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n+2, 0);
        for(int i = 0; i < n; i++){
            ans[i+1] = heights[i];
        }
        vector<int> stk(n+2, 0);
        int top = -1;
        stk[++top] = 0;
        int maxArea = 0;
        for(int i = 1; i < (n+2); i++){
            while(ans[i] < ans[stk[top]]){
                maxArea = max(maxArea,(i-stk[top-1]-1)*ans[stk[top]]);
                --top;
            }
            stk[++top] = i;
        }
        return maxArea;   
    }
};

42. 接雨水 - 力扣（LeetCode）

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n < 3){
            return 0;
        }
        stack<int> stk;
        stk.push(0);
        int ans = 0;
        for(int i = 1; i < n; i++){
            while(!stk.empty() && height[i] > height[stk.top()]){
                int mid = stk.top();
                stk.pop();
                if(!stk.empty()){
                    int left = stk.top();
                    int h = min(height[left],height[i]) - height[mid];
                    int w = i - left - 1;
                    ans += h * w; 
                }
            }
            stk.push(i);
        }
        return ans;
    }
};