思想

做完了一堆题目的动态规划专题，今天看看栈专题的内容。

栈，一个数据结构课老生常谈，在计算机系统中无处不在的数据结构，我们很熟悉了。所以这方面的题目，如果考察栈基础，难度并不是很大。其中有一类单调栈的题目，需要一定的思维量。

题目

20. Valid Parentheses

这题给了一个由各种括号组成的字符串，包括 ()、[] 和 {}，要求判断这个字符串是否合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else if (!st.empty() && 
                ((st.top() == '(' && c == ')') ||
                (st.top() == '[' && c == ']') ||
                (st.top() == '{' && c == '}'))) {
                    st.pop();
            } else {
                return false;
            }
        }

        return st.empty();
    }
};

一道 Easy 题，可以作为数据结构课的期末考试题。初始化一个栈，如果遇到左半边，直接无脑压栈。遇到右半边的时候，考虑栈顶是否与之匹配。最后，还需要判断栈是否为空。

我觉得需要理解 stack 这个 STL 容器的使用。对于各种 STL 容器，把它当作黑盒子就好，毕竟是一个抽象的数据类型。重点是掌握对其各种操作。

84. Largest Rectangle in Histogram

这题给了我们一堆柱子，问，它们组成的最大矩形的面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(0);
        int ans = 0;

        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                int currH = heights[st.top()]; st.pop();
                int left = st.empty() ? -1 : st.top();
                int width = i - left - 1;
                ans = max(ans, currH * width);
            }
            
            st.push(i);
        }

        return ans;
    }
};

乍一看，这题和双指针的最大容器题有点像，实际不一样。双指针的那道题，只在乎边界的两个柱子，但是这道题需要考虑边界之间的所有柱子。

这是道 Hard，做法是单调栈。单调栈的好处是，只有在不满足单调的时机，才需要考虑最大值的更新。

结合代码，如果不破坏单调，则无脑把索引压入。这里的单调不要求严格，不减就行。此外，注意压入的是索引，这个思想在动态规划的一道题中也有体现。压入索引相较于压入值来说，不会丢失任何信息。但是比较的时候就要注意不等号两端语义是否相同，即，不要让值和索引相比较。

如果破坏了单调，那么就需要做值的更新。结合下面的一个输入举例。

1
[1, 2, 3, *1*]

最新输入是 1，需要更新值，并维护单调栈。

首先把 3 弹出，宽度应该是 1，通过计算栈顶索引和当前索引 i 之差得到。但注意，栈顶索引是 2 的索引，而不是 3 的索引。你可以说，通过一个简单的偏移量就能完成转换，但这里的索引包含的语义信息其实很不自然：我希望计算高度对应位置和当前位置的差距，为什么要用当前高度的前一个位置作为参数？

我个人认为，这种处理是为了方便应对栈中最后一个元素的情况。

假如这样的输入：

1
[2, 1, 2]

最后栈中只有 1，栈中最后一个元素的含义很特殊。从单调栈的语义可以得到，它所在位置左侧的元素都比它高，右侧的也都比它高。它处在凹点。为了处理它，首先要在 heights 中压入 0，确保能处理最后一个元素。以及，该怎样计算这个高度？这就是当栈空时，left = -1 的含义。

如果对于栈中最后一个元素，还采用它所在位置作为下标，得到的结果是错误的，只包含了凹点右侧的值，没有包含左侧的。这和其他值的处理方式不一样。如果栈中还有值，说明左侧的都小于当前高度，只考虑右侧部分；但对于最后一个元素，必须左右都考虑。

155. Min Stack

这题算是一个小模拟。让实现一个 MinStack 类，首先是个栈，其次要在 $O(1)$ 的时间内取出栈中最小的元素。

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
class MinStack {
private:
    stack<int> st;
    stack<int> st_min;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        st.push(val);
        if (st_min.empty() || val <= st_min.top()) st_min.push(val);
    }
    
    void pop() {
        int val = st.top(); st.pop();
        if (val == st_min.top()) st_min.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return st_min.top();
    }
};

不出意外，这应该是第一次遇到模拟题。之前有个 Trie 的题，我做完了但是没写题解。

对于这种实现类的题目，如果把属性拿出来，而不放到构造函数内，会比较简洁，因为不需要各种 this->。

之后就本题来说，肯定要实现一个栈类。同时为了能够满足题目的 $O(1)$ 要求，用空间换时间，再实现一个最小栈，压入当前栈中的最小值。需要在条件判断上动动脑筋，注意是 <= 而不是 <。否则在下述例子会出错，过早地弹出了最小值。

1
2
压入 0，压入 1，压入 0，弹出，取最小值
                              ^^^^^^^^

394. Decode String

这题要求我们解码字符串。字符串用类似 3[abc]4[bc15[de]] 的方式压缩。

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
class Solution {
public:
    string decodeString(string s) {
        int num = 0;
        string curr = "";

        stack<int> intStack;
        stack<string> strStack;

        for (char c : s) {
            // num
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            }
            else if (c == '[') {  // push
                intStack.push(num);
                strStack.push(curr);

                num = 0;
                curr = "";
            }
            else if (c == ']') {  // pop
                int num = intStack.top(); intStack.pop();
                string prev = strStack.top(); strStack.pop();

                for (int i = 0; i < num; i++) {
                    prev += curr;
                }

                curr = prev;
            }
            else {
                curr += c;
            }
        }

        return curr;
    }
};

如果用状态机的思路来处理这道题，我感觉会好写一些。

一共有 4 种状态：

  1. 读取数字中；
  2. 读到 [；
  3. 读到 ]
  4. 一般字符。

注意数字可以是多位数，因此只有进入状态 2 才能盖棺定论到底系数是多少。当进入状态 2，要压入数字，以及之前处理过的字符串。状态 3 则要对重复的次数和当前字符串做解压。状态 4 比较简单，附加操作便 OK。

739. Daily Temperatures

这题给了我们一串天数的温度，要求对于每一天，计算还有多少天才能变暖。如果找不到变暖的日子，则用 0 表示。

好比冬季每天的气候罢，你没法把今天的温度加在昨天的上面，好等明天积成个和暖的春日。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st;
        vector<int> ans(n, 0);

        for (int i = 0; i < n; i++) {
            while (!st.empty() && temperatures[st.top()] < temperatures[i]) {  // warmer
                int idx = st.top(); st.pop();
                ans[idx] = i - idx;
            }
            
            st.push(i);
        }

        return ans;
    }
};

这题也是个单调栈，只不过是单调递减的。monotonic 的一些性质有时候很有用。

这次，还是在单调性被破坏的时候做一些操作，记录一下需要等多少天才能变暖。