一：最长公共子序列

image-20251021162312696

1. 动态规划

使用一个二维数组来记录以x和y长度的两个字符串的最大子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
                if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
        return dp[m][n];
    }
};

image-20251021162337154

二：编辑距离

image-20251021162354971

1. 动态规划

一共有三种替换方式，对于增加和删除是相对于原数据加1，替换有可能不增加，需要对三种方式取最小值，这里主要使用距离来表示两个字符串的差异

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; ++i)
            dp[i][0] = i;
        for (int i = 0; i <= n; ++i)
            dp[0][i] = i;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
            {
                int add = dp[i - 1][j] + 1;
                int del = dp[i][j - 1] + 1;
                int tak = dp[i - 1][j -1];
                if (word1[i - 1] != word2[j - 1]) ++tak;
                dp[i][j] = min(add, min(del, tak));
            }
        return dp[m][n];
    }
};

image-20251021162422277

三：最长有效括号

image-20251021162450990

1. 动态规划

使用一个数组来表示以右括号结尾的子串的长度，那么左括号必为0，此时右括号有两种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        vector<int> dp(len, 0);
        int result = 0;
        for (int i = 1; i < len; ++i) 
        {
            if (s[i] == ')')
                if (s[i - 1] == '(' && i >= 2)
                    dp[i] = dp[i - 2] + 2;
                else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                {
                    dp[i] = dp[i - 1] + 2;
                    int pre = i - dp[i - 1] - 2;
                    if (pre >= 0) dp[i] += dp[pre];
                }
                result = max(result, dp[i]);
        }
        return result;
    }
};

image-20251021162557296

2. 栈

这个方法相对容易但也需要一些技巧，我们使用索引放入堆栈作为未匹配字符，遇到右括号表明存在匹配从而弹出栈顶数据，使用当前位置减去栈顶未匹配索引即为所求字符串的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        stack<int> stk;
        int result = 0;
        stk.push(-1);
        for (int i = 0; i < len; ++i)
            if (s[i] == '(') stk.push(i);
            else
            {
                stk.pop();
                if (stk.empty()) stk.push(i);        // 保证有数据作为未匹配字符
                else result = max(result, i - stk.top());
            }
        return result;
    }
};

image-20251021162549113

3. 不需要额外的空间

对于一个有效的字符串一定满足两个条件，一：左右括号数量相等，二：前缀子串的左括号数不小于右括号、后缀子串右括号不小于左括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        int result = 0;
        int left = 0, right = 0;
        for (int i = 0; i < len; ++i)		// 无法处理左括号过多的情况
        {
            if (s[i] == '(') ++left;
            else ++right;
            if (left == right) result = max(result, 2 * left);
            if (right > left) left = right = 0;         // 不合法，重置
        }
        left = right = 0;
        for (int i = len - 1; i >= 0; --i)			// 无法处理右括号过多的情况
        {
            if (s[i] == '(') ++left;
            else ++right;
            if (left == right) result = max(result, 2 * left);
            if (left > right) left = right = 0;         // 不合法，重置
        }
        return result;
    }
};

image-20251021162539242

四：数据流的中位数

image-20251021162619915

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
28
29
30
31
class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> priLess;
    priority_queue<int, vector<int>, greater<int>> priGreater;
    MedianFinder() {}
    
    void addNum(int num) {
        if (priLess.empty() || num <= priLess.top())
        {
            priLess.push(num);
            if (priLess.size() > priGreater.size() + 1)
            {
                priGreater.push(priLess.top());
                priLess.pop();
            }
        } else
        {
            priGreater.push(num);
            if (priGreater.size() > priLess.size())
            {
                priLess.push(priGreater.top());
                priGreater.pop();
            }
        }
    }
    double findMedian() {
        if (priLess.size() > priGreater.size()) return priLess.top();
        return (static_cast<long long>(priLess.top()) + static_cast<long long>(priGreater.top())) / 2.0;	// 这里提升精度，否则有可能报错
    }
};

image-20251021162642837

2. 有序集合+双指针

使用multiset来维护一个有序数组，使用两个指针维护中位数，需要对双指针进行较多判断

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 MedianFinder {
public:
    multiset<int> nums;
    multiset<int>::iterator left, right;
    MedianFinder() {left = nums.end(); right = nums.end();}
    void addNum(int num) {
        int len = nums.size();
        nums.insert(num);
        if (len == 0) left = right = nums.begin();
        else if (len & 1) 
            if (num < *left) --left;
            else ++right;
        else
            if (num >= *right) ++left;
            else if (num >= *left && num < *right) 
            {
                ++left;
                --right;
            }
            else
                --right;
    }
    double findMedian() {
        return (static_cast<long long>(*left) + static_cast<long long>(*right)) / 2.0;
    }
};

image-20251021162705338

五：柱状图中最大的矩形

image-20251021162731346

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 Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        stack<int> stk;
        vector<int> left(len), right(len);
        for (int i = 0; i < len; ++i)
        {
            while (stk.empty() != true && heights[stk.top()] >= heights[i])
                stk.pop();
            left[i] = stk.empty() ? -1 : stk.top();
            stk.push(i);
        }
        stk = std::stack<int>();
        for (int i = len - 1; i >= 0; --i)
        {
            while (stk.empty() != true && heights[stk.top()] >= heights[i])
                stk.pop();
            right[i] = stk.empty() ? len : stk.top();
            stk.push(i);
        }
        int result = 0;
        for (int i = 0; i < len; ++i)
            result = max(result, (right[i] - left[i] - 1) * heights[i]);
        return result;
    }
};

image-20251021162800135

2. 单调栈+常数优化

上个方法使用了两个循环，考虑第一个循环是否发现栈顶值被弹出说明它此时已经找到了比它小的右边界，但此时需要对存储右边界的数组的初始值进行限制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        stack<int> stk;
        vector<int> left(len, -1), right(len, len);		// 从前到后只能正确处理左边界，右边界需要限定
        for (int i = 0; i < len; ++i)
        {
            while (stk.empty() != true && heights[stk.top()] >= heights[i])		// 考虑递增的数组，此时无法找到元素的右边界
            {
                right[stk.top()] = i;
                stk.pop();
            }
            left[i] = stk.empty() ? -1 : stk.top();		// 只能处理左边界
            stk.push(i);
        }
        int result = 0;
        for (int i = 0; i < len; ++i)
            result = max(result, (right[i] - left[i] - 1) * heights[i]);
        return result;
    }
};

image-20251021162816459