算法基础算法

中心扩散法

字数统计: 2.9k字   |   阅读时长: 12分
, , ,

摘要: 枚举中点，看两边能扩散多长

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文通过最长回文子串问题，看一下数组上关于子数组的问题的两种不同方向的思考方式，一种是首先确定子数组的两端 l, r，然后对子数组 $[l, r]$ 进行判断。另一种是先确定中点，然后看从中点向两侧可以扩散多长。

其中第二种，先确定中点，然后再向两边扩散是一种通用的思路，可以解决很多问题。其算法框架为首先预处理 left[i] 表示 i 向左可以扩散到的最小下标、right[i] 表示 i 向右可以扩散到的最大下标，然后枚举 i 作为中点，找到 i 向左可以扩散的最远位置 left[i]，以及向右可以扩散的最远位置 right[i]，就可以更新以 $i$ 为中心的答案。

可以看出，当已经预处理完成 left 和 right，更新答案的时间复杂度为 $O(n)$。因此难点在于如何 $O(n)$ 地预处理 left 和 right。

针对中心扩散法，后面给出了两个例题，第一题通过单调栈预处理 left 和 right，第二题用了类似前缀和的算法预处理 left 和 right 信息。

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：”bb”

提示：

1
2
1 <= s.length <= 1000
s 仅由数字和英文字母组成

算法：枚举 $[left, right]$ 然后判断

确定头和尾，判断该子串是否为回文串。

枚举头和尾 left, right 需要 $O(N^{2})$，对于每一组 [left, right]，需要 $O(N)$ 来判断是否回文。总时间复杂度为 $O(N^{3})$。

如果预处理出来 dp[i][j] 表示 [i, j] 是否构成回文串。则判断的时候只需要查询 dp[left][right] 即可。预处理的过程为区间 DP，如下：

1
2
3
4
5
6
7
8
9
状态定义
dp[i][j] := dp[i][j] 是否是回文子串

初始化
dp[i][i] = 1
dp[i][i + 1] = 1  (s[i] = s[i + 1])

状态转移
dp[i][j] = dp[i + 1][j - 1]   (s[i] == s[j])

这样预处理的时间复杂度为 $O(N^{2})$，枚举 [left, right] 的时间复杂度为 $O(N^{2})$，查询的时间复杂度为 $O(1)$，总时间复杂度 $O(N^{2})$。

代码 (C++)

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
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n == 1) 
            return s;

        vector<vector<bool> > dp(n, vector<bool>(n, 0));
        for(int i = 0; i < n; ++i)
        {
            dp[i][i] = true;
            if(i < n - 1)
                dp[i + 1][i] = true; // 处理 bb 这种情况的转移
        }

        int max_length = 1;
        int max_i = 0;
        for(int j = 1; j < n; ++j)
            for(int i = j - 1; i >= 0 ; --i)
            {
                // 没有隐含剪枝，速度没有暴力枚举快
                int len = j - i + 1;
                if(s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1];
                if(dp[i][j] && len > max_length)
                {
                    max_i = i;
                    max_length = len;
                }
            }
        return s.substr(max_i, max_length);
    }
};

算法：枚举 $mid$ 然后向两侧扩散

指定回文串的中点，看能往两侧延伸多长。

对于枚举到的 i，首先以 s[i] 为中心走一遍，再以 s[i], s[i+1] 为中心走一遍。

中心扩散的过程中，只要出现 s[i] != s[j] 的情况，扩散结束，继续扩散后的 [i, j] 就不会访问到了，相当于带了一个剪枝效果。而区间 DP 中所有的 dp[i][j] 都会访问到，因此运行时间更长。

代码 (C++)

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 Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty()) return "";
        int n = s.size();
        if(n == 1) return s;

        int max_len = 1;
        int start = 0;
        for(int i = 0; i < n; ++i)
        {
            // while 循环提前终止，相当于剪枝了一些状态
            int len1 = 1; // s[i] 为中心点的最长回文子串长
            int l = i - 1, r = i + 1;
            while(l >= 0 && r <= n - 1 && s[l] == s[r])
            {
                len1 += 2;
                ++r;
                --l;
            }
            if(len1 > max_len)
            {
                max_len = len1;
                start = l + 1;
            }
            int len2 = 0; // s[i], s[i - 1] 为中心点的最长回文子串长
            l = i - 1;
            r = i;
            while(l >= 0 && r <= n - 1 && s[l] == s[r])
            {
                len2 += 2;
                ++r;
                --l;
            }
            if(len2 > max_len)
            {
                max_len = len2;
                start = l + 1;
            }
        }
        return s.substr(start, max_len);
    }
};

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
输入： heights = [2,4]
输出： 4

提示：

1
2
1 <= heights.length <=1e5
0 <= heights[i] <= 1e4

算法：中心扩散

该问题的标准解法为单调栈，参考文章 单调栈。下面我们用中心扩散法重新解决。

枚举 $i$ 作为直方图的中点，以 heights[i] 作为矩形高度，看可以往两侧扩展多长。

向左扩展的过程：

1
2
3
l = i - 1
while(l >= 0 && heights[l] >= heights[i])
    l--;

向右扩展的过程：

1
2
3
r = i + 1
while(r < n && heights[r] >= heights[i])
    r++;

这样枚举的时间复杂度 $O(N)$，扩散的时间复杂度 O(N)，总时间复杂度 $O(N^{2})$。

如果我们可以预处理出 left[i] 表示 $i$ 向左可以扩展到的位置，right[i] 表示 $i$ 向右可以扩展到的位置，则扩散过程可以 $O(1)$ 完成：

1
2
l = left[i];
r = right[i];

下面的问题是如何 $O(N)$ 预处理 left[i] 和 right[i]。

对于 left[i]，要找的是 heights[0..i-1] 中小于 left[i] 的最右边的元素。

从小到大枚举 i，维护一个栈，其中记录了一部分 heights[0..i-1] 的下标，从栈底到栈顶，下标对应的值逐渐变大。此时要找 heights[0..i-1] 中小于 heights[i] 的最右边的元素，只需要不断弹出栈顶，直至 heights[st.top()] < heights[i] 即可。记 left[i] = st.top() + 1，然后将 i 压入。

对于 right[i]，要找的是 heights[i+1..n-1] 中小于 right[i] 的最左边元素。

从大到小枚举 i，维护一个栈，其中记录了一部分 heights[i+1..n-1] 的下标，从栈底到栈顶，下标对应的值逐渐变大。此时要找 heights[i+1..n-1] 中小于 heights[i] 的最左边的元素，只需要不断弹出栈顶，直至 heights[st.top()] < heights[i] 即可。记 right[i] = st.top() - 1，然后将 i 压入。

代码 (C++)

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();

        // 预处理
        vector<int> left(n), right(n);
        stack<int> st1, st2;
        left[0] = 0;
        st1.push(0);
        for(int i = 1; i < n; ++i)
        {
            while(!st1.empty() && heights[st1.top()] >= heights[i])
                st1.pop();
            if(st1.empty())
                left[i] = 0;
            else
                left[i] = st1.top() + 1;
            st1.push(i);
        }
        right[n - 1] = n - 1;
        st2.push(n - 1);
        for(int i = n - 2; i >= 0; i--)
        {
            while(!st2.empty() && heights[st2.top()] >= heights[i])
                st2.pop();
            if(st2.empty())
                right[i] = n - 1;
            else
                right[i] = st2.top() - 1;
            st2.push(i);
        }

        // 中心扩散
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            ans = max(ans, heights[i] * (right[i] + 1 - left[i]));
        }
        return ans;
    }
};

838. 推多米诺

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

  • dominoes[i] = ‘L’，表示第 i 张多米诺骨牌被推向左侧，
  • dominoes[i] = ‘R’，表示第 i 张多米诺骨牌被推向右侧，
  • dominoes[i] = ‘.’，表示没有推动第 i 张多米诺骨牌。

返回表示最终状态的字符串。

提示：

1
2
3
n == dominoes.length
1 <= n <= 1e5
dominoes[i] 为 'L'、'R' 或 '.'

示例 1：
输入：dominoes = “RR.L”
输出：”RR.L”
解释：第一张多米诺骨牌没有给第二张施加额外的力。

示例 2：
输入：dominoes = “.L.R…LR..L..”
输出：”LL.RR.LLRRLL..”

算法：中心扩散

对于 a[i]，若初始时为 L 或 R，则终止时不变。因此只需要看 a[i] = '.' 的这部分会怎样变化。

决定 a[i] 如何变化的是 a[i] 右侧的 L 以及其左侧的 R 哪个离得更近。如果左边的 R 离 a[i] 更近，则终止时 a[i] = R，如果右边的 L 离得更近，则终止时 a[i] = L。

但是 a[i] 左边的 R 在传导到 a[i] 的过程中可能被离 a[i] 更近的 L 挡住，如果挡住了，相当于 a[i] 的左边没有 R，类似地，也要考虑 a[i] 右边的 R 对 a[i] 右边的 L 的阻挡作用。

综上，需要预处理以下信息：

1
2
3
4
LR[i]: i 左侧最近的 R 位置
LL[i]: i 左侧最近的 L 位置
RR[i]: i 右侧最近的 R 位置
RL[i]: i 右侧最近的 L 位置

预处理的过程类似于前缀和的推导过程。

然后枚举每个位置 $i$。根据 $i$ 位置的以上四个信息更新答案。根据各个预处理信息的含义分类讨论即可，细节比较多。

代码 (C++)

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
56
57
58
59
60
class Solution {
public:
    string pushDominoes(string dominoes) {
        int n = dominoes.size();
        string &s = dominoes;

        // 预处理 
        vector<int> LL(n, INT_MIN), LR(n, INT_MIN);
        for(int i = 0; i < n - 1; ++i)
        {
            LL[i + 1] = LL[i];
            LR[i + 1] = LR[i];
            if(s[i] == 'L')
                LL[i + 1] = i;
            if(s[i] == 'R')
                LR[i + 1] = i;
        }
        vector<int> RL(n, INT_MAX), RR(n, INT_MAX);
        for(int i = n - 1; i > 0; --i)
        {
            RR[i - 1] = RR[i];
            RL[i - 1] = RL[i];
            if(s[i] == 'L')
                RL[i - 1] = i;
            else if(s[i] == 'R')
                RR[i - 1] = i;
        }

        // 中心扩散
        string result = s;
        for(int i = 0; i < n; ++i)
        {
            if(s[i] != '.') 
                continue;
            int ll = LL[i], lr = LR[i], rl = RL[i], rr = RR[i];
            if(ll == lr || rl == rr)
            {
                if(ll == lr && rl < rr)
                    result[i] = result[i] = 'L';
                else if(rl == rr && ll < lr)
                    result[i] = result[i] = 'R';
                continue;
            }
            if(ll < lr && rr < rl)
                result[i] = 'R';
            else if(lr < ll && rr < rl)
                continue;
            else if(lr < ll && rl < rr)
                result[i] = 'L';
            else
            {
                if(i - lr > rl - i)
                    result[i] = 'L';
                else if(i - lr < rl - i)
                    result[i] = 'R';
            }
        }
        return result;
    }
};
Share