【LeetCode 热题 100】有效的括号 / 最小栈 / 字符串解码 / 柱状图中最大的矩形

栈

有效的括号

• 有效的括号

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char e : s)
        {
            if (st.empty()) st.push(e);
            else if (st.top() == '(' && e == ')' || st.top() == '{' && e == '}'
                || st.top() == '[' && e == ']') st.pop();
            else st.push(e);
        }
        return st.empty();
    }
};

最小栈

• 最小栈

class MinStack {
    stack<int> st;
    stack<int> minst;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        st.push(val);
        if (minst.empty() || val <= minst.top())
        {
            minst.push(val);
        }
    }
    
    void pop() {
        if (st.top() == minst.top())
        {
            minst.pop();
        }
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }
};

字符串解码

• 字符串解码

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return dfs(s, i);
    }
    string dfs(const string& s, int& i)
    {
        string str;
        while (i < s.size() && s[i] != ']')
        {
            if (isdigit(s[i]))
            {
                int num = 0;
                while (i < s.size() && s[i] != '[')
                {
                    num = num * 10 + s[i++] - '0';
                }
                i++; // 跳过'['
                string tmp = dfs(s, i);
                i++; // 跳过']'
                while (num--) str += tmp;
            }
            else str += s[i++];
        }
        return str;
    }
};

每日温度

• 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st;
        vector<int> res(n);
        for (int i = 0; i < n; i++)
        {
            while (st.size() && temperatures[st.top()] < temperatures[i])
            {
                int t = st.top();
                st.pop();
                res[t] = i - t;
            }
            st.push(i);
        }
        return res;
    }
};

柱状图中最大的矩形

• 柱状图中最大的矩形

1. 单调递增栈：分别从左向右和从右向左遍历，找到每个柱子左边和右边第一个比它矮的柱子位置。
2. 计算宽度：对于每个柱子，其左右边界之间的距离即为矩形的宽度，高度为当前柱子的高度。
3. 求最大值：遍历所有可能的矩形，找出面积最大的一个。

单调栈。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        stack<int> st;
        for (int i = 0; i < n; i++)
        {
            while (st.size() && heights[st.top()] >= heights[i])
            {
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        st = stack<int>();
        for (int i = n - 1; i >= 0; i--)
        {
            while (st.size() && heights[st.top()] >= heights[i])
            {
                st.pop();
            }
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            res = max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
};

优化。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n, -1), right(n, n);
        stack<int> st;
        for (int i = 0; i < n; i++)
        {
            while (st.size() && heights[st.top()] > heights[i])
            {
                right[st.top()] = i;
                st.pop();
            }
            if (st.size()) left[i] = st.top(); 
            st.push(i);
        }
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            res = max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
};

堆

数组中的第K个最大元素

• 数组中的第K个最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i = n - 2 / 2; i >= 0; i--)
        {
            adjust_down(nums, i, n);
        }
        while (--k)
        {
            swap(nums[0], nums[--n]);
            adjust_down(nums, 0, n);
        }
        return nums[0];
    }
    void adjust_down(vector<int>& nums, int parent, int n)
    {
        int child = 2 * parent + 1;
        while (child < n) 
        {
            if (child + 1 < n && nums[child + 1] > nums[child]) child++;
            if (nums[child] > nums[parent])
            {
                swap(nums[child], nums[parent]);
                parent = child;
                child = 2 * parent + 1;
            }
            else break;
        }
    }
};

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~