Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

柱状图中最大的矩形 - 题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

柱状图中最大的矩形-一从暴力开始

首先，思考一下问题的解空间有多大（也就是说有多少种选择），显然一个开始位置、一个结束位置，所以我们可以得到暴力解法的思路：
（1）双层循环确定开始结束位置，也就是矩阵的长
（2）从开始到结束扫描一遍，找到最小值，也就是矩阵的宽
（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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
int largestRectangleArea(vector<int>& heights) {
    int n = height.size();
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; j++) {
            int minv = INF;
            for (int k = i; k <= j; ++k) {
                minv = min(minv, height[k]);
            }
            res = max(res, (i - j + 1) * minv);
        }
    }
    return res;
}

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> s(heights.size() + 2);
        vector<int> w(heights.size() + 2);
        int p = 0;

        heights.push_back(0);
        int res = 0;
        for (int i = 0; i < heights.size(); ++i) {
            if (heights[i] > s[p]) {
                s[++p] = heights[i];
                w[p] = 1;
            }
            else {
                int width= 0;
                while (s[p] > heights[i]) {
                    width += w[p];
                    res = max(res, width * s[p]);
                    p--;
                }
                s[++p] = heights[i];
                w[p] = width + 1;
            }
        }
        return res;
    }
};vf

public class Solution {
    public int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++)
            if (heights[minindex] > heights[i])
                minindex = i;
        return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
    }
    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }
}

int largestRectangleArea(vector<int>& heights) {
    int n = height.size();
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int minv = height[i];
        for (int j = i; j < n; j++) { //确保j从小变大
            int minv = INF;
            //如果i看作一个定值，下面这个循环，其实每次都做了相同的工作，重复扫描[i, j]
            //所以可以做累计处理
            //for (int k = i; k <= j; ++k) {
            //    minv = min(minv, height[k]);
            //}
            minv = min(minv, height[j]);
            res = max(res, (i - j + 1) * minv);
        }
    }
    return res;
}

时间复杂度：$O(n^3)$ => $O(n^2)$
空间复杂度：$O(1)$

柱状图中最大的矩形-进一步思考

还有一种解法，一种更有智慧的解法，不像前面的暴力解法那么粗暴，让我们先考虑下哪些肯定不会成为答案。
如果一个格子往两边延伸，一直延伸到有比它更低的格子为止。
柱状图中最大的矩形-分治法
如果备选答案覆盖了矩形A，那么备选答案的宽度一定会延伸到绿色矩形这里。

假设有N个像上面的这种备选答案，那么最终答案一定是出自这N个备选答案。

为什么我们这么考虑呢？ 因为这样子考虑的话，有利于我们分解子问题。

柱状图中最大的矩形-空间换时间版

1
2
3
4
5
6
7
8
9
10
11
12
int dfs(vector<int>& height, int l, int r) {
    int p = find_min(height, l, r);

    int left_lower = 0； //往左查找，直到找到比height[p]更小的元素
    int right_lower = 0；//往右查找，直到找到比height[p]更小的元素

    return max(dfs(l, p - 1), dfs(p + 1, r), height[p] * (right_lower - left_lower);
}

int largestRectangleArea(vector<int>& height) {
  return dfs(height, 0, height.size() - 1);
}

递推公式：$T(n) = 2*T(n/2) + O(n)$
时间复杂度：$O(nlgn)$
空间复杂度：$O(1)$

单调栈解法

找右边，比我小的（利用递增栈）；找到了，就可以计算候选了。

左边的都比我小，left确定了；

新来的，比我小，right也确定了； 所以面积就确定了！

Posted on Edited on In Valine:

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时，视为不能形成容器，请返回0
3.数据保证能容纳最多的水不会超过整形范围，即不会超过2^31-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int i = 0, j = height.size() - 1;
        int lmax = 0, rmax = 0;
        while (i < j) {
            lmax = max(lmax, height[i]);
            rmax = max(rmax, height[j]);
            res = max(res, min(lmax, rmax) * (j - i));
            if (lmax < rmax) {
                i++;
            } else {
                j--;
            }
        }

        return res;
    }
};

Posted on Edited on In Valine:

接雨水问题 - 题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

接雨水问题-一开始的思路

经典解法包括：
（1）单调栈，左右遇到的最大值
（2）双指针

首先，也是最重要的，先把题目搞清楚（好多时候解不出题是由于题目没有完全理解、没有理解完全或者完全没有理解）。
按照题意，一个格子能够接的水，取决于该格子向前、向后遇到的最大值，两个最大值取最小值；而我之前曾经按照往前、往后遇到的比该格子高的格子来算了。

其次，让我们考虑最暴力的做法是什么？暴力扫描。

接雨水问题-一暴力扫描代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    for (int i = 1; i < n; ++i) {

        //往左找到最大值
        int lmax = 0;
        for (int j = 0; j < i; ++j) {
            lmax = max(lmax, height[j]);
        }

        //往右找到最大值
        int rmax = 0;
        for (int j = i + 1; j < i; ++j) {
            rmax = max(rmax, height[j]);
        }

        res += min(rmax, lmax) - height[i];

    }
}

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

接雨水问题-进一步思考

观察上面的代码，有很多重复计算，例如计算i左边的最大值时，扫描范围是[0, i - 1];当计算i+1左边的最大值时，扫描范围是[0, i]，显然是完全包含[0, i - 1]的，
对于重复计算，我们继续采用空间换时间的套路，用数组lmax[i]来存储[0, i - 1]的最大值；这样子存储之后，如果再计算lmax[i + 1]只要拿lmax[i]跟height[i + 1]比较即可。

接雨水问题-空间换时间版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    int lmax[N], rmax[N];
    //正序遍历
    for (int i = 1; i < n; ++i) {
        lmax[i] = max(lmax[i - 1], height[i - 1]);
    }

    //倒序遍历 
    for (int i = n; i >= 0; --i) {
        rmax[i] = max(rmax[i + 1], height[i + 1]);
    }

    for (int i = 1; i < n; ++i) {
        res += min(lmax[i], rmax[i]) - height[i];
    }
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

接雨水问题-能不能把空间复杂度优化掉？

其实，上面的时间复杂度已经是最优了，有没有可能把空间也优化掉呢？我们注意到lmax[i]仅跟lmin[i-1]有关系，这个对于我们做空间压缩是很好的；
剩下的就是，我们能不能把lmax,rmax立即用上，而不需要存起来呢？答案是可以的。我们可以把上面的循环写在一起，用i、j两个指针分别指向左右两个端点，在遍历的过程中，直接把前面出的lmax, rmax立即用上。

接雨水问题-双指针优化版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int trap(vector<int>& height) {
    int n = height.size();
    int res = 0;
    int lmax, rmax;
    int i = 1, j = n - 2;

    while (i < j) {
        lmax = max(lmax, height[i - 1]);
        rmax = max(rmax, height[j + 1]);
        if (lmax < rmax) {
            res += lmax - height[i];
            i++;
        }
        else {
            res += rmax - height[j];
            j--;
        }
    }
    return res;
}
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 trap(vector<int>& height) {
        int lmax = 0, rmax = 0;
        int l = 0, r = height.size() - 1;
        int sum = 0;

        while (l <= r) {
            for (; l <= r && (lmax = max(height[l], lmax)) <= rmax; ++l) {
                sum += lmax - height[l];
            }
            for (; r >= l && (rmax = max(height[r], rmax)) <= lmax; r--) {
                sum += rmax - height[r];
            }
        } 

        return sum;
    }
};

时间复杂度：$O(n)$
空间复杂度：$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
28
29
30

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        stack<int> s;
        s.push(-1);
        int res = 0;
        for (int i = 0; i < arr.size(); ++i) {
            while (s.top() != -1 && arr[s.top()] < arr[i]) {
                int cur = s.top(); //当前计算的格子
                s.pop();
                int left = s.top();
                if (left >= 0) {
                    res += (min(arr[left], arr[i]) - arr[cur]) * (i - left - 1);
                    //cout << "i:" << i << ", cur:"  << cur << ", res: " << res << endl;
                }
            }

            s.push(i);
        }

        return res;
    }
};

Posted on Edited on In Valine:
  1. 前缀和和差分的本质：空间换时间
  2. 前缀和：将原来序列的O（N)的累加操作转换为O(1)的相减操作
    3.差分：将原序列O（N）的区间操作（同时加或者同时减去）转换为差分序列上的O(1)的双端操作
  3. 注意二维前缀和与二维差分

前缀和和差分，通过空间来换时间，一般用来优化时间复杂度，从$O(n^2)$到$O(n)$

//一维前缀和 —— 模板题 AcWing 795. 前缀和

1
2
3
4
int prefix_sum() {
    S[i] = a[1] + a[2] + ... a[i];
    a[l] + ... + a[r] = S[r] - S[l - 1];
}

//二维前缀和 —— 模板题 AcWing 796. 子矩阵的和

1
2
3
4
5
6
int 2d_preifx_sum()
{
    S[i, j] = 第i行j列格子左上部分所有元素的和
    //以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
    S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
}

//一维差分 —— 模板题 AcWing 797. 差分
给区间[l, r]中的每个数加上c：

1
B[l] += c, B[r + 1] -= c

//二维差分 —— 模板题 AcWing 798. 差分矩阵
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

1
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
题目分类 题目名称 考察点 其他说明
前缀和系列 不使用除法的特殊累乘 前缀和、定序技巧

Posted on Edited on In Valine:
题目分类 题目名称 考察点 其他说明
最长无重复字串 滑动窗口、字符串类 
1
2
3
4
5
6
7
8
9
//滑动窗口 模版
for (int i = 0, j = 0; i < n; i ++ )
{
    //i是新进入窗口的元素
    //[j,i]是窗口边缘，j是要滑出的下标，i是新进入的下标
    while (j < i && check(i, j)) j ++ ; //j是可能要滑出窗口的元素

    // 具体问题的逻辑
}

Posted on Edited on In Valine:

最长无重复字串 - 题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

假设字符串中只包含从’a’到’z’的字符。

样例
输入：”abcabc”

输出：3

最长无重复字串-实现思路

首先，默写下滑动窗口的模版：

1
2
3
4
5
6
7
8
9
int i = 0, j = 0, n;
while (i < n) {
    //对新进入窗口的元素i进行处理

    while (j < i && check(xx)) {
        //对出窗口的元素j进行处理
        j++;
    }
}

其次，搞清楚滑动窗口是用来做什么的以及用什么数据结构来维护

很明显，我们需要使用滑动窗口来存储每一个字母的出现次数，并且在当前窗口内的字母不重复；数据结构的话，hashmap即可

最长无重复字串-代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestSubstringWithoutDuplication(string s) {
      int i, j = 0, n =s.size();
      unordered_map<char,int> counter;
      int res = 0;
      while (i < n) {
          char c = s[i];
          counter[c]++;
          if (counter[c] == 1) { //新来了一个不重复元素，则窗口扩大了
               res = max(res, i - j + 1)
          }
          i++;
          while (j < i && counter[c] > 1) { //如果现在窗口已经不在符合条件，则一直往前移动left，直到窗口重新满足
              counter[s[j]]--;
              j++;
          }
      }
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxLength(vector<int>& arr) {
        unordered_map<int, int> counter;

        int i = 0, j = 0, res = 0;
        while (j < arr.size()) {
            counter[arr[j]]++;
            while (counter[arr[j]] > 1) {
                counter[arr[i++]]--;
            }

            res = max(j - i + 1, res);
            j++;
        }

        return res;
    }
};

Posted on Edited on In Valine: 
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:
    unordered_map<char, int> pattern;

    string minWindow(string src, string tt) {
        //将目标串转换为方便检查处理的hashmap
        for (auto x : tt) {
            pattern[x]++;
        }
        int cnt = pattern.size();

        string res;
        for (int i = 0, j = 0, c = 0; i < src.size(); ++i) {
            if (pattern[src[i]] == 1 ) c++;
            pattern[src[i]]--; //将src[i]标记为缺少状态
            //满足了，并且某一个字符是缺的【非pattern中的字符一定缺；并且一定会被补上】，则往前移动
            while (c == cnt && pattern[src[j]] < 0) {
                pattern[src[j++]]++; 
            } 
            if (c == cnt) {
                if (res.empty() || res.size() > i - j + 1) res = src.substr(j, i - j + 1);
            }
        }
        return res;
    }
};

Posted on Edited on In , Valine:

奇偶重排-题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

样例
输入：[1,2,3,4,5]

输出: [1,3,5,2,4]

Read more »