LeetCode Hot100 Stack

Posted on Edited on

有效的括号

Problem

https://leetcode.cn/problems/valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

Solution

遍历字符串，如果是左括号则进栈，如果是右括号，判断栈是否为空，非空的话判断栈顶是否为匹配的括号。

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

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

        return stk.empty();
    }
};

最小栈

Problem

https://leetcode.cn/problems/min-stack/?envType=study-plan-v2&envId=top-100-liked

Solution

维护一个存放最小值的栈

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
class MinStack {
public:
    stack<int> stk;
    stack<int> min_stk;

    MinStack() {

    }

    void push(int val) {
        stk.push(val);

        if (min_stk.empty())
        {
            min_stk.push(val);
        }
        else
        {
            min_stk.push(min(val, min_stk.top()));
        }
    }

    void pop() {
        stk.pop();
        min_stk.pop();
    }

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

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

/**
 * 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();
 */

字符串解码

Problem

https://leetcode.cn/problems/decode-string/?envType=study-plan-v2&envId=top-100-liked

Solution

遍历字符串，遇到数字累加到tempnum里，遇到字符追加到tempstr后，遇到’[‘将tempstr，tempnum进栈，遇到右括号将repstr，num出栈，将tempstr重复num次拼到repstr后面作为新的tempstr。

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
class Solution {
public:
    string decodeString(string s) {

        stack<string> str_stk;
        stack<int> num_stk;

        string temp_str;
        int temp_num = 0;

        for (const char &ch : s)
        {
            if (ch >= '0' && ch <= '9')
            {
                temp_num = temp_num * 10 + (ch-'0');
            }
            else if (ch >= 'a' && ch <= 'z')
            {
                temp_str += ch;
            }
            else if (ch == '[')
            {
                str_stk.push(temp_str);
                temp_str = "";
                num_stk.push(temp_num);
                temp_num = 0;
            }
            else // ch == ']'
            {
                string rep_str = str_stk.top();
                str_stk.pop();
                int rep_times = num_stk.top();
                num_stk.pop();
                for (int i = 0; i < rep_times; i ++)
                {
                    rep_str += temp_str;
                }
                temp_str = rep_str;
            }
        }
        return temp_str;
    }
};

每日温度

Problem

https://leetcode.cn/problems/daily-temperatures/?envType=study-plan-v2&envId=top-100-liked

Solution

维护一个单调非增的栈。

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> low_index;
        vector<int> answer(n, 0);
        for (int i = 0; i < temperatures.size(); i ++)
        {
            while (!low_index.empty() && temperatures[i] > temperatures[low_index.top()])
            {
                answer[low_index.top()] = i-low_index.top();
                low_index.pop();
            }
            low_index.push(i);
        }
        return answer;
    }
};

柱状图中的最大矩形

Problem

https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&envId=top-100-liked

Solution

包含某棵柱子的前提下，可勾勒出的矩形是从这棵柱子向左右延伸，直到遇到较矮的柱子。维护一个单调递增的单调栈（即在当前元素<=栈顶元素时出栈），从左往右遍历，找到每根柱子左边离他最近的较矮的柱子，
从右往左遍历找到每根柱子右边离他最近的较矮的柱子。

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
51
52
53
54
55
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

        int n = heights.size();
        stack<int> left_index;
        vector<int> left_bound(n, -1);
        for (int i = 0; i < n; i ++)
        {
            while (!left_index.empty() && heights[i] <= heights[left_index.top()])
            {
                left_index.pop();
            }

            if (left_index.empty())
            {
                left_bound[i] = -1;
            }
            else
            {
                left_bound[i] = left_index.top();
            }
            left_index.push(i);
        }

        stack<int> right_index;
        vector<int> right_bound(n, n);

        for (int i = n - 1; i >= 0; i --)
        {
            while (!right_index.empty() && heights[i] <= heights[right_index.top()])
            {
                right_index.pop();
            }

            if (right_index.empty())
            {
                right_bound[i] = n;
            }
            else
            {
                right_bound[i] = right_index.top();
            }

            right_index.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i ++)
        {
            ans = max(ans, heights[i] * (right_bound[i] - left_bound[i] - 1));
        }
        return ans;
    }
};